将有序数组转换为二叉搜索树 图解题解

这道题到底在问什么

nums

[-10,-3,0,5,9,12,18]

输出

以 5 为根的平衡 BST

要求

中序遍历能还原原数组

最优解：一步一步想明白

1. 3因为数组是有序的,按顺序 insert 会让树一路向右长成链表,高度 O(n),完全不平衡。
2. 4中点左边的数全比它小(进左子树),右边的全比它大(进右子树),数量还差不多——天然平衡。左右两段各自又是同样的小问题 → 递归。
3. 5盯住两件事:上方数组里当前处理的区间 [lo,hi] 和中点 mid,以及下方那棵树一格一格长出节点。
4. 6lo=0 hi=6 → mid=3整段区间是下标 [0,6]。中点 mid = 3,对应的数 5 当根。它左边 [0,2] 进左子树,右边 [4,6] 进右子树。
5. 75 落地,成为树根第一个节点 5 出现了,它是整棵树的根。接下来先把它的左半段 [0,2] 建成一棵完整子树。
6. 8lo=0 hi=2 → mid=1进入左半段 [0,2](根 5 已变灰,表示用过了)。中点 mid = 1,对应 -3,它将挂为 5 的左孩子。
7. 9-3 → 5 的左孩子-3 挂到了 5 的左下方。-3 自己又分两段:左边 [0,0] 和右边 [2,2],继续往下分。
8. 10lo=0 hi=0 → mid=0-3 的左半段缩到只剩 [0,0] 一个数。单个元素就是一个叶子:-10 挂为 -3 的左孩子。
9. 11-10 → -3 的左孩子-10 落在最左下,它的左右区间都空了,是一片叶子。-3 的左边搞定,回头处理 -3 的右边 [2,2]。
10. 12lo=2 hi=2 → mid=2回到 -3 的右半段 [2,2],也只剩一个数。0 挂为 -3 的右孩子。
11. 130 → -3 的右孩子0 落地。到这里根 5 的整棵左子树都建好了,函数才回头去建 5 的右半段 [4,6]。
12. 14lo=4 hi=6 → mid=5现在轮到根的右半段 [4,6](左边四个数都灰了)。中点 mid = 5,对应 12,挂为根 5 的右孩子。
13. 1512 → 5 的右孩子12 挂到 5 的右下方。和 -3 一样,它再分两段:左 [4,4]、右 [6,6]。
14. 16lo=4 hi=4 → mid=412 的左半段缩到 [4,4]。9 挂为 12 的左孩子。
15. 179 → 12 的左孩子9 落地。只差最后一个数 18 了——它是 12 的右半段 [6,6]。
16. 18lo=6 hi=6 → mid=6最后一段 [6,6],只剩 18,挂为 12 的右孩子。所有数都要安家了。
17. 1918 → 12 的右孩子18 落在最右下角。7 个数一格一格全长进了树里。
18. 20高度 = 3, 左右平衡 ✓树建完了:整整 3 层、左右各 3 个节点,完美平衡。每次「取中点对半分」,树就不会长歪。
19. 21走到最左下:-10验证用「中序遍历」:一路往左走到底,最先访问的是最左下的 -10。合法 BST 的中序结果该是升序,我们一个节点一个节点地点亮看看。
20. 22回到 -10 的父节点:-3-10 没有左孩子也没有右孩子,回到它的父节点 -3(根访问完才轮到右子树)。已亮的 -10 变灰,当前点亮 -3。
21. 23-3 的右孩子:0-3 的右孩子 0 被访问。整棵左子树走完了,顺序正好是 -10 → -3 → 0,全升序。接下来该轮到根 5。
22. 24左子树走完,访问根:5左子树全部访问完,才回到根 5 点亮它。这就是中序「左→根→右」里的「根」这一步。现在去走右子树。
23. 25进入右子树最左:9进入右子树,同样先走到它的最左 9(12 的左孩子)。到这里序列是 -10 → -3 → 0 → 5 → 9,依旧严格升序。
24. 2612 → 18,全部访问完最后访问 9 的父节点 12、再访问它的右孩子 18。完整中序:-10 → -3 → 0 → 5 → 9 → 12 → 18,和原数组分毫不差——确认它是合法 BST。
25. 27build(lo,mid-1) 会一路递归到底、把左边整棵子树挂好,函数才返回去执行 build(mid+1,hi)。理解这个「深入到底再回头」的顺序,递归就不再玄乎。
26. 30和二分查找是同一招:二分在有序数组上对半「查」一个数,本题在有序数组上对半「建」一棵树——想通这点,二分和分治就打通了。
27. 32右段写成 [mid,hi] → 死递归若右段误写成 build(mid, hi),mid 永远被算进去,区间永远缩不小,同一个根 5 被反复建,递归停不下来直接栈溢出。子区间必须排除 mid。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

class Solution:
    def sortedArrayToBST(self, nums):
        def build(lo, hi):
            if lo > hi:            # 区间为空 → 没有节点
                return None
            mid = (lo + hi) // 2   # 取中点当根
            root = TreeNode(nums[mid])
            root.left = build(lo, mid - 1)   # 左半段
            root.right = build(mid + 1, hi)  # 右半段
            return root
        return build(0, len(nums) - 1)

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return build(nums, 0, (int)nums.size() - 1);
    }
    TreeNode* build(vector<int>& nums, int lo, int hi) {
        if (lo > hi) return nullptr;          // 空区间
        int mid = lo + (hi - lo) / 2;         // 防溢出的中点
        TreeNode* root = new TreeNode(nums[mid]);
        root->left  = build(nums, lo, mid - 1);
        root->right = build(nums, mid + 1, hi);
        return root;
    }
};

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }
    private TreeNode build(int[] nums, int lo, int hi) {
        if (lo > hi) return null;             // 空区间
        int mid = lo + (hi - lo) / 2;         // 防溢出的中点
        TreeNode root = new TreeNode(nums[mid]);
        root.left  = build(nums, lo, mid - 1);
        root.right = build(nums, mid + 1, hi);
        return root;
    }
}

复杂度

面试官可能追问