0108. Convert Sorted Array to Binary Search Tree

题目信息

题号:
  1. 将有序数组转换为二叉搜索树

难度:

Easy

主题:

二叉搜索树、分治、有序数组、高度平衡

原题:

LeetCode 0108

重点:

从有序区间确定根的可选位置,用中点同时满足 BST 划分与高度平衡,再以索引删除切片复制

题目重述

给定一个严格递增的整数数组 nums,构造一棵高度平衡的二叉搜索树并返回根节点。

二叉搜索树要求任意节点左子树中的值都小于当前值,右子树中的值都大于当前值;高度平衡要求每个节点的左右 子树高度差不超过 1。树的中序遍历应恰好恢复 nums。满足条件的结构可能不唯一,返回任意一种即可。

数组长度在 1..10^4 范围内,元素值在 -10^4..10^4 范围内。

自建示例

  • 偶数长度:nums = [-8,-2,1,5,11,16],一种合法层序结果是 [1,-8,11,null,-2,5,16];

  • 奇数长度:nums = [2,4,6,8,10],选择 6 为根可得到左右各两个节点的平衡树;

  • 两个元素:nums = [3,9],[3,null,9] 与 [9,3] 都合法;

  • 单元素:nums = [7],返回只含节点 7 的树。

C++ 实现

#include <vector>

class Solution {
private:
    TreeNode* buildWithSlices(const std::vector<int>& values) {
        if (values.empty()) {
            return nullptr;
        }
        const int middle = static_cast<int>(values.size() - 1) / 2;
        const std::vector<int> leftValues(values.begin(), values.begin() + middle);
        const std::vector<int> rightValues(values.begin() + middle + 1, values.end());
        TreeNode* root = new TreeNode(values[middle]);
        root->left = buildWithSlices(leftValues);
        root->right = buildWithSlices(rightValues);
        return root;
    }

    TreeNode* buildFromRange(const std::vector<int>& nums, int left, int right) {
        if (left > right) {
            return nullptr;
        }
        const int middle = left + (right - left) / 2;
        TreeNode* root = new TreeNode(nums[middle]);
        root->left = buildFromRange(nums, left, middle - 1);
        root->right = buildFromRange(nums, middle + 1, right);
        return root;
    }

public:
    TreeNode* sortedArrayToBST(std::vector<int>& nums) {
        return buildFromRange(nums, 0, static_cast<int>(nums.size()) - 1);
    }
};

题解

根的选择空间

对严格递增数组选择任意元素 nums[middle] 作为根时,它左侧的全部值都小于根,右侧的全部值都大于根。 只要分别用左右连续区间构造左右子树,BST 的大小关系就会自然成立,中序遍历也会按“左区间、中点、右区间” 恢复原数组。

因此 BST 条件本身没有唯一指定根。若每次选择区间端点,例如依次把递增元素插入普通 BST,所有节点会形成 单侧链;值顺序正确,却不满足高度平衡。新信息来自平衡要求:根必须让左右两侧的元素数量尽量接近。

中点分治

选择当前连续区间的中点后,左右元素数之差最多为 1。对左右区间继续做同样选择,每个子树也由近似 对半的区间构造。buildWithSlices 直接把中点左右的值复制成两个新数组,再递归生成孩子。

这套构造同时保持三个不变量:

  • 当前节点值来自区间中点;

  • 左右递归只接收中点两侧的连续区间,因此所有值满足 BST 大小关系;

  • 每次区间规模近似减半,因此左右递归树高最多相差一层。

最后一项不能只从“左右节点数差一”推断任意两棵树高度相近,而要结合递归也始终取中点。对区间长度归纳: 长度 0、1 显然平衡;更长区间的两侧规模为 floor((n - 1) / 2) 与 ceil((n - 1) / 2),两侧都按同一规则构造,较大一侧最多比另一侧多进入一个规模层级,所以高度差不超过 1,当前根也平衡。

切片的重复搬运

切片让“中点左右分别递归”非常直观,但数组从未改变,复制只是在重复描述边界。平衡分治的每一层合计复制 O(n) 个元素,共有 O(log n) 层,因此总复制工作为 O(n log n);真正需要创建的输出节点只有 n 个。

buildFromRange 改为在原数组上传递闭区间 [left, right]。空区间满足 left > right;非空区间 计算 middle = left + (right - left) / 2,再递归处理 [left, middle - 1] 与 [middle + 1, right]。左右数组副本全部消失,每个下标只在成为某个根时读取一次。

中点与多解

奇数长度区间只有一个中点;偶数长度区间有两个居中的候选,选择任意一个都会使左右规模差为 1。代码中 的整数除法固定选择左中点,使输出可预测,但题目并不要求特定层序结构。

以 [-8,-2,1,5,11,16] 为例,初始闭区间 [0,5] 选择下标 2、值 1;左区间 [0,1] 选择值 -8,右区间 [3,5] 选择值 11。区间变化如下:

区间

中点值

左区间

右区间

[0,5]

1

[0,1]

[3,5]

[0,1]

-8

空

[1,1]

[3,5]

11

[3,3]

[5,5]

每个单元素区间生成叶节点;空区间返回 nullptr。中序访问这些递归区间时,下标顺序仍为 0,1,2,3,4,5,所以既不会遗漏输入值,也不会产生额外值。

主解与复杂度

公开入口采用索引区间方案,因为它保留中点分治的全部信息,同时删除数组切片。每个元素创建一个节点,时间 为 O(n);由于每次规模近似减半,递归栈为 O(log n)。返回树本身使用 O(n) 节点空间,不计入 额外工作空间。切片方案的树同样平衡,但总复制时间为 O(n log n),峰值还需保存数组副本。