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

简单通过率 80.6%python3核心代码模式二叉树样例通过牛客 AC树二叉搜索树数组分治二叉树

一句话

取区间中点当根，左右两半各自照办，高度天然平衡。

解题思路¶

这题考什么¶

升序数组本身就是某棵 BST（二叉搜索树）的中序遍历。反过来建树时，选谁当根决定了左右子树各分到多少元素 —— 要做到「高度平衡」，就得让两边的元素个数尽量一样多，也就是取区间的中点当根。中点两侧的个数最多差一，于是左右子树的高度最多差一，逐层递推下来整棵树自然平衡。

正确性由两条各自独立的性质保证：

BST 性质：数组严格递增，中点左边的值全部小于它、右边全部大于它；
平衡性质：区间每次对半砍，长度 n 的区间建出的树高是 O(log n)。

答案不唯一 —— 中点取靠左还是靠右都合法，题面的说明里也列了另一种答案。这份写法取靠右的中点，即 (lo + hi + 1) // 2，理由是要和题面给出的首选答案逐位对上：本题在 meta.json 的 judge 里没有条目，本地验证走严格比对，取靠左的中点会建出另一棵同样合法但形状不同的树，本地会判错（力扣线上是特判，两种都收）。

示例 1：nums = [-10,-3,0,5,9]

区间 [0,4] -> 中点下标 2 -> 根是 0
左段 [0,1] -> 中点下标 1 -> -3；它的左段 [0,0] -> -10，右段为空
右段 [3,4] -> 中点下标 4 -> 9；它的左段 [3,3] -> 5，右段为空
层序读出来是 [0,-3,9,-10,null,5]，与样例给的首选答案一致。

数据规模与复杂度¶

1 <= nums.length <= 10^4，值域 [-10^4, 10^4]，严格递增。每个元素恰好建一个节点，时间 O(n)；空间是递归深度 O(log n)， 1e4 个元素也就 14 层左右。

坑在哪¶

这题的递归是安全的，别按「树题一律改迭代」的惯性去改写。递归深度等于建出来的树高，而树高被「对半切」死死压在 log2(1e4) 约 14 层，离 CPython 默认的 1000 层上限差着两个数量级。同专题里 LC98、LC543 那种「树的形状由输入决定」的题才必须迭代。
区间用下标传，不要切片。写成 build(nums[:mid]) 每层都要复制一份数组，总复制量 O(n log n)；本题只要一对下标就够了。
中点取法会改变输出的形状。(lo + hi) // 2 得到的是另一棵合法的平衡 BST，力扣线上判特判会通过，本地严格比对会判错，理由见上。
递归出口是 lo > hi。写成 lo >= hi 会把单元素区间也当成空区间，整层叶子都建不出来。

参考实现¶

solutions/leetcode/LC108/sol.py
from typing import List, Optional


class Solution:
    def sortedArrayToBST(self, nums: List[int]) -> "Optional[TreeNode]":
        def build(lo: int, hi: int) -> "Optional[TreeNode]":
            # 出口只认「区间为空」。lo == hi 是单元素区间，仍要建一个叶子
            if lo > hi:
                return None
            # 取靠右的中点：两侧个数最多差一，保证高度平衡。
            # 那个 +1 就是「靠右」的来源，去掉会建出另一棵形状不同的合法树
            mid = (lo + hi + 1) // 2
            node = TreeNode(nums[mid])
            # 数组严格递增，中点左边全部更小、右边全部更大，BST 性质自动成立
            node.left = build(lo, mid - 1)
            node.right = build(mid + 1, hi)
            return node

        # 下标区间取闭区间 [0, n-1]；n 为 0 时 lo > hi，第一层就返回 None
        return build(0, len(nums) - 1)

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