cpp 升序数组转换为高度平衡二叉搜索树
时间: 2023-07-24 12:11:15 浏览: 53
将一个升序数组转换为高度平衡的二叉搜索树,可以采用递归的方式来实现。
具体步骤如下:
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]` 作为根节点。再递归地处理左右子数组,分别将它们转换为左右子树。最后返回根节点,构成一棵完整的二叉搜索树。
最后,我们可以使用遍历的方式打印出生成的二叉搜索树,以验证其正确性。