108. 将有序数组转换为二叉搜索树(leetcode)

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/

要点是分割左右区间,并且分割时需要注意left和right相加可能会超过int,但是本题不需要

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 有返回值写法
        TreeNode root = dfs(nums,0,nums.length);
        return root;
    }

    // 构建平衡二叉树节点,若nums仍然有余数,则继续遍历构建节点,区间左闭右开
    TreeNode dfs(int[] nums,int start,int end)
    {
        if(start>=end)return null;
        // 单层逻辑,每次取出区间中间值进行bulid,
        int mid=start+end >> 1;
        TreeNode node = new TreeNode(nums[mid]);
        // 建立连接,并构建左右子树
        node.left = dfs(nums,start,mid);
        node.right = dfs(nums,mid+1,end);
        return node;
    }
}



class Solution {
    TreeNode root;
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length>0)root = new TreeNode(nums[nums.length/2]);
        // 无返回值写法
        dfs(root,nums,0,nums.length/2);
        dfs(root,nums,nums.length/2+1,nums.length);
        return root;
    }

    // 构建平衡二叉树节点,若nums仍然有余数,则继续遍历构建节点,区间左闭右开
    void dfs(TreeNode root,int[] nums,int start,int end)
    {
        if(start>=end)return;
        // 单层逻辑,每次取出区间中间值进行bulid,
        int mid=start+end >> 1;
        TreeNode node = new TreeNode(nums[mid]);
        // 建立连接
        if(node.val > root.val)root.right = node;
        else root.left = node;
        // 构建左右子树
        dfs(node,nums,start,mid);
        dfs(node,nums,mid+1,end);
    }
}