代码随想录Day40

LeetCode108. 将有序数组转换成二叉搜索树

将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。

本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。

示例:

就像构造最大二叉树一样。我们可以取有序数组的中间节点作为根节点进行构造。如果存在两个中间节点，随便任取一个都是平衡二叉树

递归三部曲：

1.返回值和入参：

传入数组和左右下标志，返回node，根据返回的node构造中节点的左右孩子。

2.终止条件：

 空节点时，返回

3.单层递归逻辑：

取中间节点元素构造函数。

并以中间节点为界，划分左右子树。不断地递归，直到没有值时返回，返回的值构造节点。

代码：

左闭右开 [left,right)

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return sortedArrayToBST(nums, 0, nums.length);
    }
    
    public TreeNode sortedArrayToBST(int[] nums, int left, int right) {
        if (left >= right) {
            return null;
        }
        if (right - left == 1) {
            return new TreeNode(nums[left]);
        }
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = sortedArrayToBST(nums, left, mid);
        root.right = sortedArrayToBST(nums, mid + 1, right);
        return root;
    }
}

递归: 左闭右闭 [left,right]

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = traversal(nums, 0, nums.length - 1);
        return root;
    }

    // 左闭右闭区间[left, right]
    private TreeNode traversal(int[] nums, int left, int right) {
        if (left > right) return null;

        int mid = left + ((right - left) >> 1);
        TreeNode root = new TreeNode(nums[mid]);
        root.left = traversal(nums, left, mid - 1);
        root.right = traversal(nums, mid + 1, right);
        return root;
    }
}