如何通过算法练习-day20掌握长尾词的运用技巧？
- 内容介绍
- 文章标签
- 相关推荐
本文共计1154个文字，预计阅读时间需要5分钟。
二叉树+669.+修剪二叉搜索树+题目：给你二叉搜索树的一个节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树+不应该改变保留在“
二叉树
669. 修剪二叉搜索树
题意：给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该改变保留在树中的元素的相对结构 (即如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意：根节点可能会根据给定的边界发生改变。
示例：
思路：本题我们的思路是将满足判断区间的节点相连，即如上图所示，将0移除，然后拼接3和2这样的情况，因此，我们先遍历所有节点，然后找出需要拼接的节点，从下到上一层一层返回，将符合条件的节点拼接到一起，最终得到一颗符合条件的BST
C++代码：
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(nullptr==root)
{
return root;
}
if(root->val<low)//开始寻找符合条件的节点，不符合条件的节点直接跳过
{
return trimBST(root->right,low,high);
}
if(root->val>high)
{
return trimBST(root->left,low,high);
}
root->left=trimBST(root->left,low,high);//找到符合条件的节点，进行拼接
root->right=trimBST(root->right,low,high);
return root;
}
108. 将有序数组转换为二叉搜索树
题意：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例：
思路：本题的思路就比较简单了，因为我们要创建的是BST，且数组已经是增序的了。因此，我们只需要将数组的中间节点找到，即可找到对应的根节点进行连接，然后将数组分为左右子树的数组重复上述操作，直到所有数组都没有元素，完成BST的创建
C++代码：
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size()==0)//当数组为空时，代表节点连接完毕
{
return nullptr;
}
int mid=nums.size()/2;//找到中间节点，就是一棵BST的根节点
TreeNode* root=new TreeNode(nums[mid]);
vector<int> leftnums(nums.begin(),nums.begin()+mid);//分割出左右子树的元素
vector<int> rightnums(nums.begin()+mid+1,nums.end());
root->left=sortedArrayToBST(leftnums);//进行左右子树根节点的拼接
root->right=sortedArrayToBST(rightnums);
return root;
}
538. 把二叉搜索树转换为累加树
题意：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node的新值等于原树中大于或等于node.val的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例：
思路：本题由于是BST的累加，因此，我们需要从最右侧开始累加，将最大的数最先累加，以此达到累加树的效果。
我们需要先找到最右侧节点，然后进行从下到上的累加，然后再从左子树从下到上累加，因此需要使用反转的中序遍历完成此操作。
C++代码：
int cur=0;
void CMT(TreeNode* root)//先遍历到树的最右侧，然后从下往上累加节点值，然后在遍历左侧节点从下往上累加
{
if(nullptr==root)
{
return;
}
CMT(root->right);
root->val+=cur;//中间进行累加操作
cur=root->val;
CMT(root->left);
}
TreeNode* convertBST(TreeNode* root) {
CMT(root);
return root;
}
本文共计1154个文字，预计阅读时间需要5分钟。
二叉树+669.+修剪二叉搜索树+题目：给你二叉搜索树的一个节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树+不应该改变保留在“
二叉树
669. 修剪二叉搜索树
题意：给你二叉搜索树的根节点root，同时给定最小边界low和最大边界high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该改变保留在树中的元素的相对结构 (即如果没有被移除，原有的父代子代关系都应当保留)。 可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意：根节点可能会根据给定的边界发生改变。
示例：
思路：本题我们的思路是将满足判断区间的节点相连，即如上图所示，将0移除，然后拼接3和2这样的情况，因此，我们先遍历所有节点，然后找出需要拼接的节点，从下到上一层一层返回，将符合条件的节点拼接到一起，最终得到一颗符合条件的BST
C++代码：
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(nullptr==root)
{
return root;
}
if(root->val<low)//开始寻找符合条件的节点，不符合条件的节点直接跳过
{
return trimBST(root->right,low,high);
}
if(root->val>high)
{
return trimBST(root->left,low,high);
}
root->left=trimBST(root->left,low,high);//找到符合条件的节点，进行拼接
root->right=trimBST(root->right,low,high);
return root;
}
108. 将有序数组转换为二叉搜索树
题意：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
示例：
思路：本题的思路就比较简单了，因为我们要创建的是BST，且数组已经是增序的了。因此，我们只需要将数组的中间节点找到，即可找到对应的根节点进行连接，然后将数组分为左右子树的数组重复上述操作，直到所有数组都没有元素，完成BST的创建
C++代码：
TreeNode* sortedArrayToBST(vector<int>& nums) {
if(nums.size()==0)//当数组为空时，代表节点连接完毕
{
return nullptr;
}
int mid=nums.size()/2;//找到中间节点，就是一棵BST的根节点
TreeNode* root=new TreeNode(nums[mid]);
vector<int> leftnums(nums.begin(),nums.begin()+mid);//分割出左右子树的元素
vector<int> rightnums(nums.begin()+mid+1,nums.end());
root->left=sortedArrayToBST(leftnums);//进行左右子树根节点的拼接
root->right=sortedArrayToBST(rightnums);
return root;
}
538. 把二叉搜索树转换为累加树
题意：给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node的新值等于原树中大于或等于node.val的值之和。
提醒一下，二叉搜索树满足下列约束条件：
- 节点的左子树仅包含键 小于 节点键的节点。
- 节点的右子树仅包含键 大于 节点键的节点。
- 左右子树也必须是二叉搜索树。
示例：
思路：本题由于是BST的累加，因此，我们需要从最右侧开始累加，将最大的数最先累加，以此达到累加树的效果。
我们需要先找到最右侧节点，然后进行从下到上的累加，然后再从左子树从下到上累加，因此需要使用反转的中序遍历完成此操作。
C++代码：
int cur=0;
void CMT(TreeNode* root)//先遍历到树的最右侧，然后从下往上累加节点值，然后在遍历左侧节点从下往上累加
{
if(nullptr==root)
{
return;
}
CMT(root->right);
root->val+=cur;//中间进行累加操作
cur=root->val;
CMT(root->left);
}
TreeNode* convertBST(TreeNode* root) {
CMT(root);
return root;
}