0108. Convert Sorted Array to Binary Search Tree ================================================ 题目信息 -------- :题号: 0108. 将有序数组转换为二叉搜索树 :难度: 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++ 实现 -------- .. code-block:: cpp #include class Solution { private: TreeNode* buildWithSlices(const std::vector& values) { if (values.empty()) { return nullptr; } const int middle = static_cast(values.size() - 1) / 2; const std::vector leftValues(values.begin(), values.begin() + middle); const std::vector 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& 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& nums) { return buildFromRange(nums, 0, static_cast(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``。区间变化如下: .. list-table:: :header-rows: 1 * - 区间 - 中点值 - 左区间 - 右区间 * - ``[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)``,峰值还需保存数组副本。