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

2026-09-09 HGNULB 约 4 分钟

文章信息 15 个分类 · 5 个标签

分类

LeetCode CodeTop 简单 未解决 10-20 LeetCode 热题 100 面试经典 150 题 腾讯 字节 阿里 微软 美团 百度 滴滴 猿辅导

标签

数组 树 二叉树 二叉搜索树 分治

题目描述

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

题意分析

数组严格递增，需要把全部元素各使用一次，构造一棵高度平衡的二叉搜索树。二叉搜索树要求左子树所有值小于根、右子树所有值大于根；高度平衡要求每个节点的左右子树高度差不超过 1。

数组已经给出了节点的中序顺序，关键是选择根的位置。若始终取最左边的元素，树会退化成链；每次取中间元素，可以让左右两部分的规模尽量接近。答案可以不唯一。

解法：中点递归构造平衡 BST

核心思路

[!blue]

定义 build(left, right)：用闭区间 [left, right] 的全部元素构造一棵平衡二叉搜索树，并返回它的根。

取中点 mid 作为根。因为数组严格递增，左半段全部小于 nums[mid]，右半段全部大于它；只要递归把两段各自建成二叉搜索树，再接到根上，整棵树就仍满足搜索树的大小关系。

中点还把剩余元素分成长度最多相差 1 的两段。两边继续按中点划分：相同长度的区间会建出同高的子树，长度仅差 1 的区间所需的二分层数最多差 1，因此每个节点都满足高度平衡。

区间为空时返回空节点；区间只有一个元素时仍要创建节点，它的两个子区间都会为空。递归只传下标，不需要复制数组，也不需要先插入节点再调整平衡。

解题步骤

1. 从整个数组调用 build(0, nums.length - 1)。
2. 若 left > right，当前区间为空，返回空节点。
3. 计算 mid = left + (right - left) / 2，用 nums[mid] 创建根节点。
4. 用 [left, mid - 1] 递归构造左子树，用 [mid + 1, right] 递归构造右子树，并接到根上。
5. 返回当前根节点，由上一层把它连接为自己的子树。

代码实现

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length - 1);
    }

    private TreeNode build(int[] nums, int left, int right) {
        if (left > right) {
            return null;
        }

        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);

        // 中点已用作根，两个子区间都必须排除它。
        root.left = build(nums, left, mid - 1);
        root.right = build(nums, mid + 1, right);

        return root;
    }
}

func sortedArrayToBST(nums []int) *TreeNode {
    var build func(int, int) *TreeNode
    build = func(left int, right int) *TreeNode {
        if left > right {
            return nil
        }

        mid := left + (right-left)/2
        root := &TreeNode{Val: nums[mid]}
        // 中点已用作根，两个子区间都必须排除它。
        root.Left = build(left, mid-1)
        root.Right = build(mid+1, right)
        return root
    }
    return build(0, len(nums)-1)
}

复杂度分析

• 时间复杂度：$O(n)$。每个数组元素恰好创建一个树节点。
• 空间复杂度：$O(\log n)$，不计返回的树；区间每层近似减半，递归栈深度为树高。

关键点总结

[!green]

• 有序性保证中点两侧的值分别属于左右子树，逐层递归保留搜索树性质。
• 在每层都从中点切分，让整棵树各处的高度都保持平衡。
• 一个下标恰好成为一次根，左右递归区间不重叠，因此每个元素恰好使用一次。

易错点总结

[!yellow]

• 中点已经成为根，两个子区间必须排除它；否则既可能重复建节点，也可能让区间无法缩小。
• 终止条件是 left > right。left == right 是需要创建叶子节点的有效区间。
• 偶数长度区间取左中点或右中点都合法，输出树形不必与示例完全相同。
• 空间复杂度只计算额外递归栈；返回的树本身还需要 $O(n)$ 个节点。

相似题目

题目	难度	关联与区别
109. 有序链表转换二叉搜索树	中等	同样取有序序列中间元素建平衡BST，原题链表缺少随机访问，可用中序构造避免反复找中点。
1382. 将二叉搜索树变平衡	中等	原题先从已有BST获得有序序列，再复用本题的中点分治重建。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/80396602

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！