108 将有序数组转换为二叉搜索树

一、题目

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。

二、题解

思路： 分治 + 递归。

• 由于数组已升序，取中点作为根节点就能让左右两侧元素数量尽量均衡，从而保证树的平衡。
• 中点 mid = left + (right - left) / 2 的值作为根，左半区间 [left, mid-1] 递归构造左子树，右半区间 [mid+1, right] 递归构造右子树。
• 当 left > right 时区间为空，返回 null 作为递归边界。

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        // 直接调用辅助函数，初始区间为整个数组的最左边界 (0) 和最右边界 (nums.length - 1)
        return helper(nums, 0, nums.length - 1);
    }

    // 【辅助函数：递归造树】
    public TreeNode helper(int[] nums, int left, int right) {
        // 【递归边界】如果左边界跑到了右边界的右边，说明这个区间里已经没有数字了，返回空节点
        if (left > right) {
            return null;
        }

        // 【核心逻辑 1：找中点】
        int mid = left + (right - left) / 2;

        // 【核心逻辑 2：安家落户】
        // 拎出中间的数字，把它变成当前的根节点
        TreeNode root = new TreeNode(nums[mid]);

        // 【核心逻辑 3：分发家产（递归）】
        // 根节点左边的位置，交给左半边数组 (left 到 mid - 1) 去继续造树
        root.left = helper(nums, left, mid - 1);

        // 根节点右边的位置，交给右半边数组 (mid + 1 到 right) 去继续造树
        root.right = helper(nums, mid + 1, right);

        // 这棵以 root 为根的子树造好了，向上级汇报（返回）
        return root;
    }
}

时间复杂度：$O(n)$（每个数组元素恰好被访问并创建为一个节点一次）

空间复杂度：$O(\log n)$（递归栈深度，平衡树的高度为 $O(\log n)$，返回的树本身不计入）