跳到主要内容

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

本节目标

选择有序区间中点为根，递归构造高度平衡的二叉搜索树。

这道题把构造与二叉搜索树中的有序约束直接用于构造一棵高度平衡的 BST。

查看 LeetCode 原题

题意与边界​

给定严格递增数组，构造任意一棵高度平衡的 BST。空区间返回空树；单元素区间的中点就是叶子。题目允许偶数长度区间选两个中点中的任一个。

中点就是根​

对于半开区间 [left, right)，选择 middle = left + (right - left) / 2。数组左半部分全部小于中点值，右半部分全部大于中点值，天然满足 BST 条件；两段长度最多相差一，使每层递归都尽量均分。

正确性依据​

空区间返回空树正确。中点左侧所有元素小于根，右侧所有元素大于根；递归构造的左右子树分别保持 BST 性质，故整棵树是 BST。两个递归区间长度相差至多一，并且内部也按同样规则划分，因此所有节点的左右高度差不超过一。

代码实现​

C++17
#include <vector>

using namespace std;

class Solution {
private:
    TreeNode* buildBalanced(const 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 = buildBalanced(nums, left, middle);
        root->right = buildBalanced(nums, middle + 1, right);
        return root;
    }

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

复杂度分析​

每个数组元素恰好成为一个节点，时间复杂度为 O(n)。递归栈深度为 O(log n)，不计输出树的额外空间为 O(log n)。

易错点​

  • 选固定端点作根，可能得到单侧链而不是平衡树。
  • 用闭区间和半开区间混写，导致中点重复进入子问题或漏掉元素。
  • 复制左右子数组而非传递下标边界。

模式迁移​

有序数组的中点递归也常用于分治和二分结构构造。若要求特定形状或最小高度之外的额外性质，需要把选择根的位置纳入状态。