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

2026-09-09 HGNULB 约 4 分钟

文章信息 15 个分类 6 个标签

分类

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

题目描述

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

题意分析

输入是一个严格升序的整数数组，输出是一棵二叉搜索树，并且这棵树必须「高度平衡」，也就是任意一个节点的左右子树高度差不超过 $1$。

题面给了两个关键信号。第一个信号是「升序」：二叉搜索树的中序遍历必然是升序序列，所以输入数组其实已经把答案的中序遍历顺序完全钉死了，剩下要决定的只有「谁当根」。第二个信号是「高度平衡」：一个节点当了根之后，数组里排在它前面的元素全部落进左子树，排在它后面的元素全部落进右子树，两边元素个数直接由根的位置决定；要让两边高度尽量接近，就只能让两边的元素个数尽量接近，也就是取区间的中点当根。

边界要看清楚：数组长度可能只有 $1$，此时答案是单节点树；题目允许返回任意一棵满足条件的树，所以中点在偶数长度区间上取左中位还是右中位都算对，不必纠结与示例输出是否逐字相同。

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

核心思路

有序数组已经给出了二叉搜索树的中序遍历。若每次选择区间中点作为根，中点左侧的值全部进入左子树，右侧的值全部进入右子树，既满足 BST 的大小关系，也让左右子树的节点数最多相差 $1$。

递归契约是：build(left, right) 用闭区间 [left, right] 的全部元素构造一棵高度平衡 BST，且其中序遍历与该区间完全一致。空区间返回空节点；非空区间取中点建根，再用左右两段递归构造左右子树。

正确性可由区间长度归纳：左右区间仍有序，所以递归得到合法 BST，且所有左侧值小于根、右侧值大于根；两段长度最多相差 $1$，递归又以相同方式均分，因此左右子树高度最多相差 $1$。若按升序逐个插入，树会退化成右链，无法满足平衡要求。

解题步骤

定义 build(left, right) 处理闭区间；若 left > right，返回空节点。

计算安全中点 mid = left + (right - left) / 2，用 nums[mid] 创建根节点。

递归构造左子树 [left, mid - 1]。

递归构造右子树 [mid + 1, right]。

返回根节点，入口调用 build(0, nums.length - 1)。

例如 [-10,-3,0,5,9] 首先选择 0 为根，左右区间分别是 [-10,-3] 和 [5,9]；继续取各区间中点，得到的树中序遍历仍是原数组，且每层都近似均分。

代码实现

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)$，不计返回的树；区间每层近似减半，递归栈深度为树高。

关键点总结

有序数组对应 BST 的中序遍历，中点决定根，左右区间自然对应左右子树。

每层取中点使左右规模最多相差 $1$，从构造过程保证高度平衡。

只传下标边界，不复制子数组，才能保持 $O(n)$ 时间和 $O(\log n)$ 额外空间。

偶数长度区间取左中点或右中点都合法，因此答案不唯一。

易错点总结

子区间仍包含 mid，例如右侧写成 [mid, right]，会使区间无法缩小并无限递归。

终止条件只判断 left == right，无法处理递归产生的空区间；必须使用 left > right。

按升序逐个插入会得到一条右斜链，不满足高度平衡。

每层复制左右子数组会增加时间和空间开销，直接传区间下标即可。

不要强求与示例树形完全一致；偶数区间选择不同中点会得到不同但都正确的答案。

相似题目

题目	难度	考察点
105. 从前序与中序遍历序列构造二叉树	中等	前序定根、中序分区
106. 从中序与后序遍历序列构造二叉树	中等	后序倒序定根
109. 有序链表转换二叉搜索树	中等	链表快慢指针找中点
889. 根据前序和后序遍历构造二叉树	中等	构造结果不唯一
剑指 Offer 07. 重建二叉树	中等	哈希表加速定位根
面试题 04.02. 最小高度树	简单	同型题、最小高度