LeetCode 力扣热题100 将有序数组转换为二叉搜索树
class Solution {
public:
// 主函数，输入一个有序数组 nums，返回构造的平衡二叉搜索树
TreeNode* sortedArrayToBST(vector<int>& nums) {
// 调用帮助函数，传入整个数组的范围
return help(nums, 0, nums.size() - 1);
}
// 辅助函数，递归构建二叉树
TreeNode* help(vector<int>& nums, int left, int right) {
// 基本情况：当 left > right 时，说明该子树为空，返回 nullptr
if (left > right) return nullptr;
// 计算当前子数组的中间元素索引
int mid = (left + right) / 2;
// 创建当前根节点，值为中间元素
TreeNode* root = new TreeNode(nums[mid]);
// 递归构建左子树，范围为 [left, mid-1]
root->left = help(nums, left, mid - 1);
// 递归构建右子树，范围为 [mid+1, right]
root->right = help(nums, mid + 1, right);
// 返回当前构建的树
return root;
}
};思路分析
这个问题的目的是将一个有序数组转换成一个高度平衡的二叉搜索树（BST）。二叉搜索树的特点是每个节点的值大于其左子树的所有节点值，且小于右子树的所有节点值。高度平衡的二叉搜索树是指对于每一个节点，其左子树和右子树的高度差不超过 1。
根据这个要求，可以用分治法来构建树。我们可以将数组的中间元素作为树的根节点，然后递归地将左半部分和右半部分的子数组作为左右子树进行构建。
好的，让我们深入一步，详细跟踪程序在构建平衡二叉搜索树时的运行步骤。我们使用数组 nums = [-10, -3, 0, 5, 9] 来演示整个过程。
输入：
vector<int> nums = {-10, -3, 0, 5, 9};
第一步：初始化
我们调用 sortedArrayToBST(nums)，该函数会调用 help(nums, 0, 4)（整个数组的范围）。
sortedArrayToBST(nums) // 调用 help(nums, 0, nums.size()-1)
第二步：第一次调用 help(nums, 0, 4)
输入范围：left = 0, right = 4
计算中间元素索引：
mid = (0 + 4) / 2 = 2
当前元素：nums[2] = 0
创建根节点 TreeNode* root = new TreeNode(0)。
然后递归调用：
• 构建左子树：help(nums, 0, 1)
• 构建右子树：help(nums, 3, 4)
第三步：第二次调用 help(nums, 0, 1)（构建左子树）
输入范围：left = 0, right = 1
计算中间元素索引：
mid = (0 + 1) / 2 = 0
当前元素：nums[0] = -10
创建节点 TreeNode* root = new TreeNode(-10)。
然后递归调用：
• 构建左子树：help(nums, 0, -1) → 由于 left > right，返回 nullptr，左子树为空。
• 构建右子树：help(nums, 1, 1)
第四步：第三次调用 help(nums, 1, 1)（构建右子树的右子树）
输入范围：left = 1, right = 1
计算中间元素索引：
mid = (1 + 1) / 2 = 1
当前元素：nums[1] = -3
创建节点 TreeNode* root = new TreeNode(-3)。
然后递归调用：
• 构建左子树：help(nums, 1, 0) → 由于 left > right，返回 nullptr，左子树为空。
• 构建右子树：help(nums, 2, 1) → 由于 left > right，返回 nullptr，右子树为空。
第五步：回到第二次调用 help(nums, 0, 1)（继续构建左子树）
现在左子树已经完全构建：节点 -10 的左子树是 nullptr，右子树是节点 -3。
TreeNode* root = new TreeNode(-10);
root->left = nullptr;
root->right = new TreeNode(-3);
第六步：返回到第一次调用 help(nums, 0, 4)（继续构建右子树）
接下来我们构建右子树。递归调用 help(nums, 3, 4)。
第七步：第四次调用 help(nums, 3, 4)（构建右子树）
输入范围：left = 3, right = 4
计算中间元素索引：
mid = (3 + 4) / 2 = 3
当前元素：nums[3] = 5
创建节点 TreeNode* root = new TreeNode(5)。
然后递归调用：
• 构建左子树：help(nums, 3, 2) → 由于 left > right，返回 nullptr，左子树为空。
• 构建右子树：help(nums, 4, 4)
第八步：第五次调用 help(nums, 4, 4)（构建右子树的右子树）
输入范围：left = 4, right = 4
计算中间元素索引：
mid = (4 + 4) / 2 = 4
当前元素：nums[4] = 9
创建节点 TreeNode* root = new TreeNode(9)。
然后递归调用：
• 构建左子树：help(nums, 4, 3) → 由于 left > right，返回 nullptr，左子树为空。
• 构建右子树：help(nums, 5, 4) → 由于 left > right，返回 nullptr，右子树为空。
第九步：回到第四次调用 help(nums, 3, 4)（继续构建右子树）
现在右子树已经完全构建：节点 5 的左子树是 nullptr，右子树是节点 9。
TreeNode* root = new TreeNode(5);
root->left = nullptr;
root->right = new TreeNode(9);
第十步：回到第一次调用 help(nums, 0, 4)（继续构建整个树）
现在右子树已经完全构建：节点 0 的左子树是节点 -10，右子树是节点 5。
最终二叉搜索树如下：
0
/ \
-10 5
\ \
-3 9
结论
我们已经根据有序数组 [-10, -3, 0, 5, 9] 构建出了一个平衡的二叉搜索树。每次递归通过选择中间元素来保证树的平衡性。通过递归函数 help，从根节点到叶子节点逐步构建子树，最终完成树的构建。