1. 修剪二叉搜索树
- LeetCode 链接
给你二叉搜索树的根节点 root ,同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树,使得所有节点的值在[low, high]中。
修剪树不应该改变保留在树中的元素的相对结构 (即,如果没有被移除,原有的父代子代关系都应当保留)。 可以证明,存在唯一的答案 。
所以结果应当返回修剪好的二叉搜索树的新的根节点。注意,根节点可能会根据给定的边界发生改变。
class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root == NULL) return root;
// 因为是二插搜索树,因此当前节点小于最小阈值的时候,左子树的点左分支节点都小于low,因此都会被删除
// 如果当前节点的值大于high,当前节点连带右子树的右分支 都需要被删除
// 如果小于 最小值,应该递归
if(root->val < low){
TreeNode* left = trimBST(root->right, low, high);
return left;
}
if(root->val > high){
TreeNode* right = trimBST(root->left, low, high);
return right;
}
root->left = trimBST(root->left, low, high);
root->right = trimBST(root->right, low, high);
return root;
}
};
2.将有序数组转换为二叉搜索树
- LeetCode链接
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
- 使用了额外的辅助空间
class Solution {
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size() == 0) return NULL;
// 1. 寻找中间节点 和 左右节点的分界线
int mid = nums.size() / 2;
TreeNode* root = new TreeNode(nums[mid]);
// 2. 使用迭代器创建vector
vector<int> left_vec(nums.begin(), nums.begin()+mid);
vector<int> right_vec(nums.begin()+mid+1, nums.end());
root->left = sortedArrayToBST(left_vec);
root->right = sortedArrayToBST(right_vec);
return root;
}
};
- 没有使用额外辅助空间的方法
class Solution {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
3. 把二叉搜索树转换为累加数
- LeetCode链接文章来源:https://www.toymoban.com/news/detail-447423.html
给出二叉 搜索 树的根节点,该树的节点值各不相同,请你将其转换为累加树(Greater Sum Tree),使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。文章来源地址https://www.toymoban.com/news/detail-447423.html
class Solution {
private:
int pre = 0; // 记录前一个节点的数值
void traversal(TreeNode* cur){
if(cur == NULL) return ;
traversal(cur->right);
cur->val += pre;
pre = cur->val;
traversal(cur->left);
}
public:
TreeNode* convertBST(TreeNode* root) {
pre = 0;
traversal(root);
return root;
}
};
到了这里,关于第23天-代码随想录刷题训练-第六章 ● 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!