题目描述给你一个整数数组nums其中元素已经按升序排列请你将其转换为一棵平衡二叉搜索树BST。平衡二叉搜索树左右两个子树的高度差的绝对值不超过 1每个节点的左右子树都是平衡二叉树二叉搜索树的中序遍历结果是一个升序序列正好和输入数组的顺序一致核心思路分治递归 中序遍历还原要构造一棵平衡的 BST核心是每次选择数组的中间元素作为根节点这样可以保证左右子树的节点数量尽可能相等从而天然满足平衡条件。分治逻辑递归终止条件当数组区间为空左边界 右边界时返回nullptr选择根节点取数组中间位置的元素作为当前子树的根节点递归构造左右子树左子树使用数组[left, mid-1]区间的元素构造右子树使用数组[mid1, right]区间的元素构造返回根节点左右子树构造完成后返回当前根节点完整代码实现Ccpp/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { // 调用分治函数初始区间为整个数组 [0, nums.size()-1] return build(nums, 0, nums.size() - 1); } private: // 分治递归函数在区间 [left, right] 内构造平衡BST TreeNode* build(vectorint nums, int left, int right) { // 1. 递归终止条件区间为空返回空节点 if (left right) return nullptr; // 2. 选择中间元素作为根节点避免溢出用 left (right-left)/2 代替 (leftright)/2 int mid left (right - left) / 2; TreeNode* root new TreeNode(nums[mid]); // 3. 递归构造左子树区间 [left, mid-1] root-left build(nums, left, mid - 1); // 4. 递归构造右子树区间 [mid1, right] root-right build(nums, mid 1, right); // 5. 返回当前子树的根节点 return root; } };详细执行流程解析我们以示例nums [-10,-3,0,5,9]为例模拟递归执行过程1. 第一次递归根节点构造区间[0, 4]对应数组全部元素中间位置mid 0 (4-0)/2 2对应元素nums[2] 0构造根节点0左子树区间[0,1]右子树区间[3,4]2. 构造左子树区间[0,1]中间位置mid 0 (1-0)/2 0对应元素nums[0] -10构造节点-10左子树区间[0,-1]空返回nullptr右子树区间[1,1]递归构造右子树区间[1,1]中间位置mid1对应元素nums[1] -3构造节点-3左右区间均为空返回节点-3节点-10的右子树为-3返回节点-103. 构造右子树区间[3,4]中间位置mid 3 (4-3)/2 3对应元素nums[3] 5构造节点5左子树区间[3,2]空返回nullptr右子树区间[4,4]递归构造右子树区间[4,4]中间位置mid4对应元素nums[4] 9构造节点9左右区间均为空返回节点9节点5的右子树为9返回节点54. 最终结果根节点0的左子树为-10右子树为5形成平衡二叉搜索树和示例输出一致。关键细节与易错点中间位置的计算方式推荐使用mid left (right-left)/2而不是(leftright)/2。当left和right很大时(leftright)可能会溢出导致整数越界前者可以有效避免这个问题。平衡条件的保证每次选择中间元素作为根节点会将数组分成两个长度差不超过 1 的子区间因此左右子树的高度差永远不会超过 1天然满足平衡 BST 的要求。中序遍历的一致性构造的 BST 的中序遍历结果和原数组的顺序完全一致这是 BST 的核心性质也是分治递归的基础。节点的创建与内存管理题目只要求返回根节点因此不需要额外处理内存释放。在实际工程中需要手动释放节点避免内存泄漏。复杂度分析时间复杂度(O(n))其中 n 为数组的长度。每个元素都会被访问一次创建一个节点。空间复杂度(O(log n))其中 n 为数组的长度。递归调用栈的深度等于树的高度由于是平衡树高度为 (log n)最坏情况下数组长度为 1为 (O(1))。拓展迭代版实现可选如果不想使用递归也可以用迭代的方式队列模拟递归栈实现核心逻辑和递归一致cppclass Solution { public: TreeNode* sortedArrayToBST(vectorint nums) { if (nums.empty()) return nullptr; // 队列中存储当前节点、区间左边界、区间右边界 queuetupleTreeNode*, int, int q; // 1. 创建根节点 int mid nums.size() / 2; TreeNode* root new TreeNode(nums[mid]); q.emplace(root, 0, nums.size() - 1); while (!q.empty()) { auto [node, left, right] q.front(); q.pop(); int curMid left (right - left) / 2; // 构造左子树 if (left curMid - 1) { int leftMid left (curMid - 1 - left) / 2; TreeNode* leftChild new TreeNode(nums[leftMid]); node-left leftChild; q.emplace(leftChild, left, curMid - 1); } // 构造右子树 if (curMid 1 right) { int rightMid curMid 1 (right - (curMid 1)) / 2; TreeNode* rightChild new TreeNode(nums[rightMid]); node-right rightChild; q.emplace(rightChild, curMid 1, right); } } return root; } };总结将有序数组转换为平衡二叉搜索树核心就是利用分治思想每次选择中间元素作为根节点保证左右子树的节点数量尽可能均衡从而构造出平衡的 BST。这种方法时间复杂度为线性空间复杂度为对数级是最优解之一。
