二叉树合集（六）：高度平衡的二叉搜索树简介(图文解析）

将一个升序数组转换为高度平衡的二叉搜索树，可以采用递归的方式来实现。 具体步骤如下： 1. 找到数组的中间元素，作为二叉搜索树的根节点。 2. 将数组分成左右两个子数组，左子数组中的元素都小于根节点，右子数组中的元素都大于根节点。 3. 递归地处理左右子数组，分别将它们转换为左右子树。 4. 将左右子树挂在根节点下，构成一棵完整的二叉搜索树。 以下是代码示例： ```cpp #include <iostream> #include <vector> using namespace std; struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; class Solution { public: TreeNode* sortedArrayToBST(vector<int>& nums) { return buildBST(nums, 0, nums.size() - 1); } private: TreeNode* buildBST(vector<int>& nums, int left, int right) { if (left > right) { return NULL; } int mid = (left + right) / 2; TreeNode* root = new TreeNode(nums[mid]); root->left = buildBST(nums, left, mid - 1); root->right = buildBST(nums, mid + 1, right); return root; } }; int main() { vector<int> nums = {1, 2, 3, 4, 5, 6, 7}; Solution solution; TreeNode* root = solution.sortedArrayToBST(nums); // 遍历打印二叉树 return 0; } ``` 在这个示例中，我们定义了一个 `Solution` 类，其中包含了一个 `sortedArrayToBST` 函数，用于将升序数组转换为高度平衡的二叉搜索树。 我们在 `sortedArrayToBST` 函数中调用了 `buildBST` 函数，用于递归地构建二叉搜索树。`buildBST` 函数的参数中，`nums` 表示原始数组， `left` 和 `right` 表示当前处理的数组区间。 在 `buildBST` 函数中，首先判断当前区间是否为空，如果为空则返回 `NULL`。然后计算出当前区间的中间位置 `mid`，将 `nums[mid]` 作为根节点。再递归地处理左右子数组，分别将它们转换为左右子树。最后返回根节点，构成一棵完整的二叉搜索树。 最后，我们可以使用遍历的方式打印出生成的二叉搜索树，以验证其正确性。