LeetCode 面试题 04.02. 最小高度树

2022-04-01 HGNULB 约 9 分钟

文章信息 7 个分类 5 个标签

分类

LeetCode CodeTop 简单未解决 1-2 字节跳动程序员面试金典（第 6 版）

题目描述

✅ 面试题 04.02. 最小高度树

题意分析

给定一个元素各不相同、且已按升序排列的整数数组，要求用它构造一棵二叉搜索树，并且这棵树的高度要尽可能小。题目允许返回任意一棵满足条件的树，判题用的是"高度是否最小 + 中序遍历是否等于原数组"的校验，而不是逐节点比对某棵标准答案。

约束里给了两个关键信号。第一，输入已经有序——这等于把 BST 最重要的性质（中序遍历升序）直接摆在面前，说明不需要做任何比较或插入排序，节点的相对顺序已经定死了。第二，要求高度最小——n 个节点的二叉树高度下界是 $\lceil \log_2(n+1) \rceil$，要达到这个下界，每一层都必须尽量填满，也就是任意节点的左右子树规模差不超过 1。

把这两条合起来：中序序列固定为原数组，同时要求左右子树尽量均衡。选定根之后，中序序列被根切成左右两段，这两段的长度就是左右子树的节点数；要让它们尽量均衡，根就必须取在（近似）中点。这一步推理是本题的全部难点，剩下的都是递归的机械展开。

边界上要覆盖：空数组（返回空树）；单元素；偶数长度（中点有两个候选，取哪个都行，只要一致）；以及递归区间收缩到 lo > hi 时必须终止。

解法：分治选中点构造 BST

核心思路

先想暴力：把数组元素一个个插进一棵普通 BST。瓶颈在于插入顺序完全决定形态——按升序插入会得到一条向右退化的链，高度是 $n$，是最差而非最优；即使随机打乱插入，期望高度是 $O(\log n)$ 但没有最坏保证，而且改变了"用给定数组构造"的语义。

关键观察分两步。其一，BST 的中序遍历必须升序，而输入数组本身就是升序的，所以最终树的中序遍历必然等于这个数组——节点的中序位置是被输入锁死的，我们唯一能选的只有"谁当根"。其二，一旦选定 nums[mid] 当根，中序序列 nums[lo..hi] 就被切成 nums[lo..mid-1]（左子树）和 nums[mid+1..hi]（右子树），左右子树的节点数分别是 mid - lo 和 hi - mid。要让树高最小，就要让这两个数尽量接近，于是 mid 必须取区间中点。

由此得到递归定义：build(lo, hi) 返回"用 nums[lo..hi] 这段升序子数组构造出的、高度最小的 BST 的根"。它满足两条性质——中序遍历恰为 nums[lo..hi]；高度为 $\lceil \log_2(hi - lo + 2) \rceil$。递推关系是 build(lo, hi) = 以 nums[mid] 为根，左孩子接 build(lo, mid-1)，右孩子接 build(mid+1, hi)，终止条件是 lo > hi 时返回空。

为什么"每层取中点"就能达到高度下界？因为每次递归都把区间长度砍成两半（相差至多 1），区间长度 len 经过 $\lceil \log_2(len+1) \rceil$ 层就必然收缩到空，而这正是 len 个节点的二叉树高度的理论下界，所以取中点既是可行解也是最优解。同时，取中点为根天然满足 BST 性质：左段全部小于 nums[mid]、右段全部大于它，这是输入有序直接给的，不需要额外校验。

解题步骤

入口调用 build(nums, 0, nums.length - 1)，用闭区间 [lo, hi] 表示"当前要处理的这段子数组"。选闭区间是因为它和"mid 属于当前段"的语义最贴合；用左闭右开也行，但终止条件和 mid 的计算都要跟着改，混用是本题最常见的越界来源。

递归第一步：lo > hi 时返回 null。这对应"这段子数组为空，不需要节点"。注意判断是 > 而不是 >=：lo == hi 时区间里还有一个元素，必须建出一个叶子节点；写成 >= 会把所有叶子都丢掉，构造出的树只有一半的节点。

取 mid = lo + (hi - lo) / 2。写成这个形式而不是 (lo + hi) / 2，是为了避免 lo + hi 在大数组上溢出 int（虽然本题规模小不会触发，但这是必须养成的习惯）。除法向下取整意味着偶数长度时取左中点，这不影响正确性——右中点同样能得到最小高度，只是形态不同，判题两者都接受。

用 nums[mid] 建根节点。这是"选中点当根"的落地，也是保证均衡的唯一动作。

左孩子递归 build(lo, mid - 1)，右孩子递归 build(mid + 1, hi)。两个区间必须排除 mid 本身，否则元素会被重复建成节点，中序遍历不再等于原数组，同时区间不收缩会导致无限递归直至爆栈。

返回根节点。递归自底向上把子树逐层挂上，最终得到整棵树。

以 nums = [-10, -3, 0, 5, 9] 走一遍（下标 0..4）：

build(0, 4)：mid = 0 + (4 - 0) / 2 = 2，根节点是 nums[2] = 0。左子树处理 [0, 1]，右子树处理 [3, 4]。

build(0, 1)：mid = 0 + (1 - 0) / 2 = 0，节点值 nums[0] = -10。左子树 build(0, -1)：lo > hi 返回空。右子树 build(1, 1)：mid = 1，节点值 nums[1] = -3；它的左右分别是 build(1, 0) 和 build(2, 1)，都因 lo > hi 返回空，所以 -3 是叶子。于是左子树是"根 -10，右孩子 -3"。

build(3, 4)：mid = 3 + (4 - 3) / 2 = 3，节点值 nums[3] = 5。左子树 build(3, 2) 为空；右子树 build(4, 4) 建出叶子 nums[4] = 9。于是右子树是"根 5，右孩子 9"。

最终形态：根 0，左孩子 -10（其右孩子 -3），右孩子 5（其右孩子 9）。高度是 3，而 5 个节点的高度下界是 $\lceil \log_2 6 \rceil = 3$，达到下界。中序遍历依次访问 -10, -3, 0, 5, 9，与原数组一致，BST 性质成立。

顺带验证 lo > hi 这个终止条件的必要性：build(0, -1) 中 lo = 0、hi = -1，若误写成 lo >= hi 才返回空，那么 build(1, 1) 会被直接判空，-3 这个节点根本不会被创建，中序遍历少了一个元素。

代码实现

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;
    }
}

func sortedArrayToBST(nums []int) *TreeNode {
    return build(nums, 0, len(nums)-1)
}

func build(nums []int, lo, hi int) *TreeNode {
    if lo > hi {
        return nil
    }
    mid := lo + (hi-lo)/2
    root := &TreeNode{Val: nums[mid]}
    root.Left = build(nums, lo, mid-1)
    root.Right = build(nums, mid+1, hi)
    return root
}

复杂度分析

时间复杂度：$O(n)$。每个数组元素恰好被用来创建一个节点、且只被访问一次；递归调用次数是节点数的常数倍（每个节点带来两次子调用，其中空区间的调用也是常数次），没有任何重复计算或回溯。

空间复杂度：$O(\log n)$（不计返回的树本身）。递归栈深度等于树高，而取中点保证了树是平衡的，树高为 $O(\log n)$。如果把构造出的 n 个节点也算进去，则是 $O(n)$。

关键点总结

有序输入 + BST，等价于"中序序列已被锁定"。看到这两个条件同时出现，就该立刻意识到唯一的自由度是"谁当根"，问题从"怎么构造"变成"怎么切分"，难度直接降一个档次。

要高度最小，就让每次切分尽量均衡。这是分治类构造题的通用准则：递归深度由"每层规模缩减的比例"决定，只有对半砍才能拿到 $O(\log n)$ 的深度；偏一点点（比如总是取 lo）就退化成 $O(n)$ 的链。

闭区间递归的三件套要配套写：终止条件 lo > hi、中点 lo + (hi - lo) / 2、子区间 [lo, mid-1] 与 [mid+1, hi]。三者中任意一处按另一种区间约定来写，都会导致漏节点、重复节点或无限递归。

子区间必须严格收缩且排除已用元素。mid 已经被消费成根节点，两侧区间都要跳过它。凡是递归分治，写完子调用后应立刻检查"子问题规模是否严格小于父问题"，这是防止爆栈的机械检查。

面试视角：主动说明"答案不唯一"和高度下界。面试官常追问"取右中点行不行""为什么这样就是最小高度"。标准答法是：偶数长度时左右中点都可行，判题只校验高度与中序；最小高度等于 $\lceil \log_2(n+1) \rceil$，均衡切分每层规模减半，恰好达到这个下界。能顺带补一句"若输入换成有序链表（109 题），因为不能 $O(1)$ 随机访问，要么先转数组，要么用快慢指针找中点、或用中序模拟递归"，展示对同一模型不同载体的迁移能力。

易错点总结

错误写法：终止条件写成 if (lo >= hi) return null; → 用例 nums = [1, 2]：build(0, 1) 取 mid = 0 建出节点 1，右子树 build(1, 1) 被直接判空，节点 2 丢失，中序遍历只有 [1]，判题失败。

错误写法：终止条件写成 if (lo > hi) return new TreeNode(0);（返回哨兵节点而非空） → 用例 nums = [1]：叶子节点 1 的左右各挂上一个值为 0 的假节点，中序遍历变成 [0, 1, 0]，既破坏 BST 性质又多出节点。

错误写法：mid = lo（总取左端点当根） → 用例 nums = [1, 2, 3, 4, 5]：每层只砍掉一个元素，构造出一条全右链，高度是 5 而不是 3，虽然中序遍历正确，但不满足"高度最小"，判题直接失败。

错误写法：左右递归写成 build(lo, mid) 和 build(mid, hi)（没排除 mid） → 用例 nums = [1, 2]：build(0, 1) 取 mid = 0，左子树递归 build(0, 0) 又建一个 1，右子树 build(0, 1) 与父调用完全相同，区间不收缩，无限递归直至 StackOverflowError。

错误写法：mid = (lo + hi) / 2 → 本题数据规模小不会出事，但在 lo、hi 接近 Integer.MAX_VALUE 的同类二分题上，lo + hi 溢出成负数，mid 变成负下标，直接数组越界。应统一写成 lo + (hi - lo) / 2。

错误写法：入口写成 build(nums, 0, nums.length) → 用例 nums = [1]：build(0, 1) 中 mid = 0 正常，但右子树 build(1, 1) 会访问 nums[1] 越界抛异常。闭区间的右端必须是 length - 1。

错误写法：先对 nums 调一次 Arrays.sort 保险 → 用例 nums = [-10, -3, 0, 5, 9]：结果虽然正确，但白白付出 $O(n \log n)$ 的代价，并且暴露了"没读出输入已有序这个关键条件"，面试里会被直接指出。

错误写法：把根的左右孩子接反，写成 root.left = build(mid + 1, hi) → 用例 nums = [1, 2, 3]：根是 2，左孩子挂上 3、右孩子挂上 1，中序遍历变成 [3, 2, 1]，BST 性质完全破坏。

错误写法：Go 里写成 root := &TreeNode{Val: mid}（把下标当成了值） → 用例 nums = [-10, -3, 0, 5, 9]：根节点的值变成 2 而不是 0，整棵树的值域和原数组毫无关系。构造节点时要用 nums[mid] 而非 mid。

错误写法：为了"避免递归"改成用一个队列层序建树，但按数组顺序依次取值 → 用例 nums = [1, 2, 3, 4, 5]：层序填充得到根 1、左 2、右 3……虽然形态平衡、高度是 3，但中序遍历是 [4, 2, 5, 1, 3]，完全不是升序，BST 性质不成立。形态平衡和中序有序必须同时满足，只顾一头就会错。

相似题目

题目	难度	考察点
108. 将有序数组转换为二叉搜索树	简单	完全同题的主站版本，可拿来对照两种取中点方式的不同形态
109. 有序链表转换二叉搜索树	中等	载体换成链表后无法 $O(1)$ 取中点，需快慢指针或中序模拟递归
105. 从前序与中序遍历序列构造二叉树	中等	根由前序首元素给定而非自选，重点在中序里定位根来切分左右规模
106. 从中序与后序遍历序列构造二叉树	中等	根取自后序末元素，递归时要倒着消费后序序列
889. 根据前序和后序遍历构造二叉树	中等	缺少中序导致答案不唯一，要靠前序次元素定位左子树规模
剑指 Offer 07. 重建二叉树	中等	与 105 同模型，重点是用哈希表把中序定位从 $O(n)$ 降到 $O(1)$