今日算法（构造二叉搜索树）

题目描述

给你一个整数数组nums，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树（BST）。

平衡二叉搜索树：

• 左右两个子树的高度差的绝对值不超过 1
• 每个节点的左右子树都是平衡二叉树
• 二叉搜索树的中序遍历结果是一个升序序列，正好和输入数组的顺序一致

---

核心思路：分治递归 + 中序遍历还原

要构造一棵平衡的 BST，核心是每次选择数组的中间元素作为根节点，这样可以保证左右子树的节点数量尽可能相等，从而天然满足平衡条件。

分治逻辑

1. 递归终止条件：当数组区间为空（左边界 > 右边界）时，返回nullptr
2. 选择根节点：取数组中间位置的元素作为当前子树的根节点
3. 递归构造左右子树：
   • 左子树：使用数组[left, mid-1]区间的元素构造
   • 右子树：使用数组[mid+1, right]区间的元素构造
4. 返回根节点：左右子树构造完成后，返回当前根节点

---

完整代码实现（C++）

cpp

/** * 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(vector<int>& nums) { // 调用分治函数，初始区间为整个数组 [0, nums.size()-1] return build(nums, 0, nums.size() - 1); } private: // 分治递归函数：在区间 [left, right] 内构造平衡BST TreeNode* build(vector<int>& nums, int left, int right) { // 1. 递归终止条件：区间为空，返回空节点 if (left > right) return nullptr; // 2. 选择中间元素作为根节点（避免溢出，用 left + (right-left)/2 代替 (left+right)/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. 递归构造右子树：区间 [mid+1, 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]）：
  • 中间位置mid=1，对应元素nums[1] = -3
  • 构造节点-3，左右区间均为空，返回节点-3
• 节点-10的右子树为-3，返回节点-10

3. 构造右子树（区间[3,4]）

• 中间位置mid = 3 + (4-3)/2 = 3，对应元素nums[3] = 5
• 构造节点5，左子树区间[3,2]（空，返回nullptr），右子树区间[4,4]
• 递归构造右子树（区间[4,4]）：
  • 中间位置mid=4，对应元素nums[4] = 9
  • 构造节点9，左右区间均为空，返回节点9
• 节点5的右子树为9，返回节点5

4. 最终结果

根节点0的左子树为-10，右子树为5，形成平衡二叉搜索树，和示例输出一致。

---

关键细节与易错点

1. 中间位置的计算方式推荐使用mid = left + (right-left)/2，而不是(left+right)/2。当left和right很大时，(left+right)可能会溢出导致整数越界，前者可以有效避免这个问题。

2. 平衡条件的保证每次选择中间元素作为根节点，会将数组分成两个长度差不超过 1 的子区间，因此左右子树的高度差永远不会超过 1，天然满足平衡 BST 的要求。

3. 中序遍历的一致性构造的 BST 的中序遍历结果，和原数组的顺序完全一致，这是 BST 的核心性质，也是分治递归的基础。

4. 节点的创建与内存管理题目只要求返回根节点，因此不需要额外处理内存释放。在实际工程中，需要手动释放节点避免内存泄漏。

---

复杂度分析

• 时间复杂度：(O(n))，其中 n 为数组的长度。每个元素都会被访问一次，创建一个节点。
• 空间复杂度：(O(log n))，其中 n 为数组的长度。递归调用栈的深度等于树的高度，由于是平衡树，高度为 (log n)，最坏情况下（数组长度为 1）为 (O(1))。

---

拓展：迭代版实现（可选）

如果不想使用递归，也可以用迭代的方式（队列模拟递归栈）实现，核心逻辑和递归一致：

cpp

class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { if (nums.empty()) return nullptr; // 队列中存储：当前节点、区间左边界、区间右边界 queue<tuple<TreeNode*, 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。这种方法时间复杂度为线性，空间复杂度为对数级，是最优解之一。