有序数组构造平衡二叉搜索树

题目描述

给定一个严格递增的整数列表 nums，将它转换为一棵高度平衡的二叉搜索树，返回根节点。列表可以包含负数或0，不包含重复值；不修改原列表，也不通过重新排序改变输入。

二叉搜索树要求：每个节点左子树中的值都小于该节点值，右子树中的值都大于该节点值。高度平衡要求：每个节点的左右子树高度之差不超过1。空树高度为0，单节点树高度为1。

列表下标从0开始；空列表返回 None。为固定本篇示例的构造结果，内部使用半开区间 [lo, hi)，选取 mid = (lo + hi) // 2 对应的元素作为根；偶数长度时选两个中间元素中靠右的一个。

示例：

输入： [-10, -3, 0, 5, 9]
输出的树：
          0
        /   \
      -3     9
      /     /
    -10    5

层序表示： [0, -3, 9, -10, None, 5]

主任务返回树节点；代码另提供层序序列化函数，按从上到下、每层从左到右的顺序输出，用 None 表示空位置并去掉末尾连续的空位置，方便核对。空树的层序表示为 []。

同一有序列表可能对应多棵合法的平衡搜索树；其他构造结果只要满足题意也可以。本篇过程与代码统一使用上述中点规则。

题目分析

选中间元素，再构造左右子树

输入已经严格递增。选中间元素作为根后，前面的所有值都更小，可以用于构造左子树；后面的所有值都更大，可以用于构造右子树。

左右子列表仍然有序，与原问题具有相同结构，因此可以分别递归构造。中点选择使左右子问题规模最多相差1，避免不断选择端点导致树退化成一条长链。

与合并排序相比，两者都按位置分解，但本题输入已排好序，不需要再合并数值列表。当前层创建一个根节点，把子调用返回的两棵树连接到它的左右孩子，便完成结果合成。

定义函数、空区间与边界

内部函数 build(lo, hi) 返回由 nums[lo:hi] 中的元素构造的子树根节点。代码用区间下标表达这一任务，不实际创建输入切片。

• 当 lo >= hi 时，区间为空，返回 None。
• 否则选 mid = (lo + hi) // 2，创建值为 nums[mid] 的根节点。
• 左子树使用 [lo, mid)。
• 右子树使用 [mid + 1, hi)。

两侧都排除了已选中的根元素，因此既不会重复创建节点，也不会遗漏其他元素。单元素区间会创建一个节点，再通过两个空区间调用得到空的左右孩子。

为什么同时满足搜索树与平衡条件

如果左右子调用已经分别构造了正确的搜索树，左子树所有值小于当前根，右子树所有值大于当前根，所以连接后仍是二叉搜索树。空区间与单节点提供了正确边界。

对于这一反复取中点的构造，含 $s>0$ 个节点的子树高度为 $\lfloor\log_2 s\rfloor+1$，空树高度为0。当前根的左右子树规模最多相差1，按该构造得到的高度也最多相差1；每个子调用继续使用同一规则，因此所有节点都满足高度平衡条件。

高度平衡不要求所有叶子位于同一层，也不要求树一定是完全二叉树。核对时应检查每个节点的两侧高度，而不是仅观察根节点。

实现代码

Python 递归构造与结果输出

以下代码可以独立运行。sorted_array_to_bst 返回根节点，serialize_level_order 仅负责将结果转为可打印的层序列表。输入按题目约定保证严格递增。

from collections import deque


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


def sorted_array_to_bst(nums):
    """将严格递增列表构造成平衡搜索树，不修改输入。"""
    def build(lo, hi):
        if lo >= hi:
            return None

        mid = (lo + hi) // 2
        root = TreeNode(nums[mid])
        root.left = build(lo, mid)
        root.right = build(mid + 1, hi)
        return root

    return build(0, len(nums))


def serialize_level_order(root):
    """返回保留内部空位置、去掉尾部空位置的层序列表。"""
    if root is None:
        return []

    result = []
    queue = deque([root])
    while queue:
        node = queue.popleft()
        if node is None:
            result.append(None)
        else:
            result.append(node.val)
            queue.append(node.left)
            queue.append(node.right)

    while result and result[-1] is None:
        result.pop()
    return result


if __name__ == "__main__":
    cases = [[-10, -3, 0, 5, 9], [1, 3], [7], []]
    for nums in cases:
        root = sorted_array_to_bst(nums)
        print(f"{nums} -> {serialize_level_order(root)}")

输出：

[-10, -3, 0, 5, 9] -> [0, -3, 9, -10, None, 5]
[1, 3] -> [3, 1]
[7] -> [7]
[] -> []

None 表示没有节点，不能用0代替，因为0可以是合法节点值。构造函数使用局部的 root 连接子树，各次调用创建不同的节点对象；输入列表只被读取。

层序输出中的空位置有助于还原结构。例如示例里的 None 表示节点 -3 的右孩子为空，后面的5是节点9的左孩子。

算法执行过程

递归调用：选择根并划分区间

以 [-10, -3, 0, 5, 9] 为例：

build(0, 5)：mid=2，创建根0
├── build(0, 2)：mid=1，创建根-3
│   ├── build(0, 1)：mid=0，创建根-10
│   │   └── 左右区间均为空 → 两个孩子均为None
│   └── build(2, 2) → None
└── build(3, 5)：mid=4，创建根9
    ├── build(3, 4)：mid=3，创建根5
    │   └── 左右区间均为空 → 两个孩子均为None
    └── build(5, 5) → None

当前层先创建根，等待左子树构造完成，再构造右子树，最后返回当前根。图中的左右分支表示不同子任务，并非同时执行。

递归返回：连接子树并核对高度

当前区间	根值	左子树根	右子树根	左、右子树高度	当前子树高度
[0, 1)	-10	None	None	0、0	1
[0, 2)	-3	-10	None	1、0	2
[3, 4)	5	None	None	0、0	1
[3, 5)	9	5	None	1、0	2
[0, 5)	0	-3	9	2、2	3

每行左右高度差都不超过1。对整棵树进行中序遍历，得到 [-10, -3, 0, 5, 9]，与输入一致，也核对了搜索树的顺序与元素完整性。

偶数长度与空列表

输入 [1, 3] 时，区间 [0, 2) 的 mid = 1，选3作为根，左子树是1，右子树为空。它仍然高度平衡；以1为根、3为右孩子的另一棵树也合法，但不是当前代码的输出。

输入空列表时，第一次调用就是 build(0, 0)，直接返回 None，没有创建任何节点；序列化后得到 []。

复杂度分析

设输入元素个数为 $n$。按一次索引、节点构造和指针连接为常数时间计费，不包含打印数字文本的字符长度。

时间复杂度

每个元素恰好创建一个节点，空区间只做常数工作。取根后，左右子问题规模之和为 $n-1$，所以：

$$T(n)=T(\lfloor n/2\rfloor)+T(n-1-\lfloor n/2\rfloor)+O(1), \qquad T(0)=O(1).$$

对非空输入，构造时间为 $\Theta(n)$，空列表为常数时间。虽然树高和递归深度是对数级，但所有 $n$ 个元素都要处理，不能把构造时间写成 $O(\log n)$。

层序序列化也为 $O(n)$：每个实际节点出队一次，并将两个孩子加入队列；空孩子只出队，不再扩展。最终打印的列表长度为 $O(n)$。

辅助空间复杂度

构造过程中只沿一条调用链展开，递归栈深度为 $O(\log(n+1))$，且没有复制输入区间，因此构造函数的辅助空间为 $O(\log(n+1))$。

返回的树本身含 $n$ 个新节点，需要 $O(n)$ 输出空间；如果把输出树也计入总额外存储，构造过程是 $O(n)$ 空间。不要将输出节点数量误当成递归栈深度。

序列化是独立的展示步骤，队列与返回列表的空间为 $O(n)$；因此完整示例程序的额外存储仍为 $O(n)$，不能把包含序列化的整个程序说成只占对数空间。

易错点

易错点	正确理解
忽略输入有序且无重复的条件	左值严格小于根、右值严格大于根的证明依赖题目约定
总选第一个或最后一个元素作为根	单侧可能过长；中点划分保持左右规模接近
右区间从 mid 开始	根已经使用，右区间从 mid + 1 开始
空区间仍访问 nums[mid]	先判断 lo >= hi，返回 None
用节点值的真假判断有无节点	0是合法值，应检查节点是否为 None
认为高度平衡一定是完全二叉树	两者定义不同；本题检查每个节点的左右高度差
将某一种层序输出当成唯一答案	不同中点规则可能得到不同的合法树，本篇固定一种规则便于核对
把总时间当作递归深度	每个元素都要创建节点，总时间线性
只给整个示例程序写对数空间	构造栈、输出树、序列化队列与列表需要分别计算

课堂练习

1. 按本篇中点规则构造 [1, 2, 3, 4]，写出根节点、左右子树和层序结果。
2. 对区间 [0, 5)，为什么右子区间是 [3, 5)？如果写成 [2, 5)，会出现什么问题？
3. 输入 []、[0] 时，构造函数与序列化函数各返回什么？
4. 输入 [1, 3] 时，以1为根、3为右孩子是否符合题意？本篇代码会产生它吗？
5. 构造1000个元素的树，为什么节点存储为线性级，调用栈却是对数级？

参考答案

1. 根为3；左子树根为2，左孩子为1；右子树根为4。层序结果为 [3, 2, 4, 1]。
2. 中点为2，该元素已作为根，所以右段必须从3开始。写成 [2, 5) 会把根值再次放入右子树，重复创建元素，并破坏严格的搜索树条件。
3. 空列表构造返回 None，序列化返回 []；[0] 构造返回值为0的单节点，序列化返回 [0]。
4. 符合题意，左右高度差为1且满足搜索树顺序。本篇代码选择靠右中点，返回以3为根、1为左孩子的树。
5. 每个输入元素对应一个新节点，共1000个；递归每层规模约减半，同一时刻只保存一条调用路径，因此栈深度按对数增长。序列化时的队列与输出列表另占线性空间。

相关学习：同时求数组的最大值与最小值、最长公共前缀、合并排序、递归与分治。