LeetCode 面试题 04.02. 最小高度树

约 4 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 程序员面试金典（第 6 版） 字节
标签
数组 树 二叉树 二叉搜索树 分治

题目描述

✅ 面试题 04.02. 最小高度树

image-20260929105744223

题意分析

给定元素各不相同的升序数组，用全部元素构造一棵高度最小的二叉搜索树。既要保证任意节点的左子树都更小、右子树都更大，也要避免把大量节点集中到一侧形成长链。

解法：分治选中点构造 BST

核心思路

[!blue]
每次取中点作根，将左右两段递归构造成子树。 定义 build(nums, lo, hi) 返回闭区间 [lo, hi] 对应的树。选中点 mid 后，左段全部小于 nums[mid]，右段全部大于它；只要递归得到的左右子树也符合搜索树性质，连接起来的整棵树就合法。

为什么取中点能使高度最小？高度按层数计时，$h$ 层二叉树最多容纳 $2^h-1$ 个节点，所以 $n$ 个节点至少需要 $\lceil\log_2(n+1)\rceil$ 层。中点划分使左右数量相差至多 1，最大的子问题只含 $\lfloor n/2\rfloor$ 个节点；每层继续这样平分，恰好达到上述最小层数，因此得到的是最优高度，不只是局部看起来平衡。

中点已经作为当前根使用，左递归范围必须是 [lo, mid - 1]，右递归范围必须是 [mid + 1, hi]。两侧不重叠且恰好覆盖剩余元素，每个元素只创建一个节点。空区间返回空节点；单元素区间仍需创建叶子，它的两侧递归随后自然结束。

解题步骤

  1. 从整个闭区间 [0, nums.length - 1] 开始递归，lo > hi 时返回空节点。
  2. 用 lo + (hi - lo) / 2 取中点，以该位置的元素值创建根节点。
  3. 递归构造中点左侧、右侧区间，并分别接到根的左右孩子。
  4. 返回根节点。偶数长度时选两个中点中的任意一个都能达到最优高度；空数组则从第一步直接返回空树。

代码实现

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+1)$，每个元素恰好创建一个节点，空数组直接返回。
  • 空间复杂度：递归辅助空间 $O(\log(n+1)+1)$，输出树另占 $O(n)$。

关键点总结

[!green]

  • 数组顺序对应最终中序顺序。
  • 选择中点控制高度，左右区间控制搜索树性质。
  • 偶数长度的两个中点都可用于最优构造。

易错点总结

[!yellow]

  • 单元素区间直接返回空：漏掉叶子节点。
  • 子区间仍包含中点：重复创建节点，甚至无法结束递归。
  • 把中点下标当成节点值：树中元素不再对应输入。
  • 左右子区间连接反了：高度可能正确，但搜索树顺序错误。

相似题目

题目 难度 关联与区别
109. 有序链表转换二叉搜索树 中等 同样取有序序列中间元素建平衡BST，原题链表缺少随机访问，可用中序构造避免反复找中点。
1382. 将二叉搜索树变平衡 中等 原题先从已有BST获得有序序列，再复用本题的中点分治重建。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/60758343
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！