C++算法练习-day49——108.将有序数组转换为二叉搜索树
题目来源:. - 力扣(LeetCode)
题目思路分析
题目要求将一个有序数组转换为一棵平衡二叉搜索树(BST)。平衡二叉搜索树的定义是:一个二叉搜索树,其中每个节点的两个子树的高度差不会超过1。
解题思路如下:
- 递归构建:使用递归的方法,从数组的中间元素开始构建树。选择中间元素作为当前子树的根节点,可以确保左右子树的大小尽量平衡。
- 分治策略:将数组分成左右两部分,左半部分用于构建当前节点的左子树,右半部分用于构建当前节点的右子树。
- 终止条件:递归的终止条件是数组的左右索引相遇或交错,此时应返回nullptr,表示该部分没有节点需要构建。
代码:
#include <vector>
using namespace std;
// 二叉树节点定义
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:
// 递归函数,将数组nums中索引left到right的部分构建为BST
TreeNode* ArrayToBST(vector<int>& nums, int left, int right) {
// 终止条件:如果left大于right,说明当前部分没有节点
if (left > right) {
return nullptr;
}
// 计算中间索引
int mid = (left + right) / 2;
// 创建当前子树的根节点
TreeNode* node = new TreeNode(nums[mid]);
// 递归构建左子树
node->left = ArrayToBST(nums, left, mid - 1);
// 递归构建右子树
node->right = ArrayToBST(nums, mid + 1, right);
// 返回当前子树的根节点
return node;
}
// 主函数,调用递归函数构建整棵BST
TreeNode* sortedArrayToBST(vector<int>& nums) {
// 从数组的第一个元素到最后一个元素构建BST
TreeNode* root = ArrayToBST(nums, 0, nums.size() - 1);
return root;
}
};
知识点摘要
- 二叉搜索树(BST):一种特殊的二叉树,其中每个节点的值都大于其左子树所有节点的值,且小于其右子树所有节点的值。
- 平衡二叉搜索树:每个节点的两个子树的高度差不会超过1的BST。
- 递归:一种解决问题的方法,通过函数调用自身来解决子问题,最终将子问题的解合并得到原问题的解。
- 分治策略:将一个大问题分成若干个小问题分别解决,然后将子问题的解合并得到原问题的解。
通过将有序数组的中间元素作为当前子树的根节点,并递归构建左右子树,可以有效地将有序数组转换为平衡二叉搜索树。这种方法利用了分治策略,将大问题分解为小问题,从而简化了问题的复杂度。递归的使用使得代码更加简洁和易于理解。此外,这种方法的时间复杂度为O(n),空间复杂度为O(log n)(由于递归调用栈的深度),是构建平衡二叉搜索树的一种高效方法。