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

因为数组是有序的,按顺序 insert 会让树一路向右长成链表,高度 O(n),完全不平衡。

中点左边的数全比它小(进左子树),右边的全比它大(进右子树),数量还差不多——天然平衡。左右两段各自又是同样的小问题 → 递归。

盯住两件事:上方数组里当前处理的区间 [lo,hi] 和中点 mid,以及下方那棵树一格一格长出节点。

整段 [0,6] · 取中点：整段区间是下标 [0,6]。中点 mid = 3,对应的数 5 当根。它左边 [0,2] 进左子树,右边 [4,6] 进右子树。

根诞生 · 5：第一个节点 5 出现了,它是整棵树的根。接下来先把它的左半段 [0,2] 建成一棵完整子树。

左段 [0,2] · 取中点：进入左半段 [0,2](根 5 已变灰,表示用过了)。中点 mid = 1,对应 -3,它将挂为 5 的左孩子。

挂左孩子 · -3：-3 挂到了 5 的左下方。-3 自己又分两段:左边 [0,0] 和右边 [2,2],继续往下分。

-3 的左段 [0,0]：-3 的左半段缩到只剩 [0,0] 一个数。单个元素就是一个叶子:-10 挂为 -3 的左孩子。

挂叶子 · -10：-10 落在最左下,它的左右区间都空了,是一片叶子。-3 的左边搞定,回头处理 -3 的右边 [2,2]。

-3 的右段 [2,2]：回到 -3 的右半段 [2,2],也只剩一个数。0 挂为 -3 的右孩子。

挂叶子 · 0：0 落地。到这里根 5 的整棵左子树都建好了,函数才回头去建 5 的右半段 [4,6]。

右段 [4,6] · 取中点：现在轮到根的右半段 [4,6](左边四个数都灰了)。中点 mid = 5,对应 12,挂为根 5 的右孩子。

挂右孩子 · 12：12 挂到 5 的右下方。和 -3 一样,它再分两段:左 [4,4]、右 [6,6]。

12 的左段 [4,4]：12 的左半段缩到 [4,4]。9 挂为 12 的左孩子。

挂叶子 · 9：9 落地。只差最后一个数 18 了——它是 12 的右半段 [6,6]。

12 的右段 [6,6]：最后一段 [6,6],只剩 18,挂为 12 的右孩子。所有数都要安家了。

挂叶子 · 18：18 落在最右下角。7 个数一格一格全长进了树里。

建树完成：树建完了:整整 3 层、左右各 3 个节点,完美平衡。每次「取中点对半分」,树就不会长歪。

中序遍历验证 · 访问 -10：验证用「中序遍历」:一路往左走到底,最先访问的是最左下的 -10。合法 BST 的中序结果该是升序,我们一个节点一个节点地点亮看看。

中序遍历验证 · 访问 -3：-10 没有左孩子也没有右孩子,回到它的父节点 -3(根访问完才轮到右子树)。已亮的 -10 变灰,当前点亮 -3。

中序遍历验证 · 访问 0：-3 的右孩子 0 被访问。整棵左子树走完了,顺序正好是 -10 → -3 → 0,全升序。接下来该轮到根 5。

中序遍历验证 · 访问根 5：左子树全部访问完,才回到根 5 点亮它。这就是中序「左→根→右」里的「根」这一步。现在去走右子树。

中序遍历验证 · 访问 9：进入右子树,同样先走到它的最左 9(12 的左孩子)。到这里序列是 -10 → -3 → 0 → 5 → 9,依旧严格升序。

中序遍历验证 · 访问 12 与 18：最后访问 9 的父节点 12、再访问它的右孩子 18。完整中序:-10 → -3 → 0 → 5 → 9 → 12 → 18,和原数组分毫不差——确认它是合法 BST。

build(lo,mid-1) 会一路递归到底、把左边整棵子树挂好,函数才返回去执行 build(mid+1,hi)。理解这个「深入到底再回头」的顺序,递归就不再玄乎。

和二分查找是同一招:二分在有序数组上对半「查」一个数,本题在有序数组上对半「建」一棵树——想通这点,二分和分治就打通了。

雷区实演 · 子区间含 mid：若右段误写成 build(mid, hi),mid 永远被算进去,区间永远缩不小,同一个根 5 被反复建,递归停不下来直接栈溢出。子区间必须排除 mid。

边界三连：偶数个元素时,中点取左中或右中都对(题目允许多解),只要保持平衡即可。

面试追问：递归出口、复杂度、多解性,是这题面试常被追的三点。