代码随想录算法训练营第23天|669. 修剪二叉搜索树|108.将有序数组转换为二叉搜索树|538.把二叉搜索树转换为累加树|总结篇
669. 修剪二叉搜索树
这道题目比较难,比 添加增加和删除节点难的多,建议先看视频理解。
题目链接/文章讲解:
https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html 视频讲解: https://www.bilibili.com/video/BV17P41177ud
/**
* Definition for a binary tree node.
* 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:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root==nullptr)return nullptr;
if(root->val<low)
{
TreeNode* right=trimBST(root->right,low,high);// 寻找符合区间[low, high]的节点
return right;
}
if(root->val>high)
{
TreeNode* left=trimBST(root->left,low,high);// 寻找符合区间[low, high]的节点
return left;
}
root->left=trimBST(root->left,low,high);// root->left接入符合条件的左孩子
root->right=trimBST(root->right,low,high);// root->right接入符合条件的右孩子
return root;
}
};
108.将有序数组转换为二叉搜索树
本题就简单一些,可以尝试先自己做做。
https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1uR4y1X7qL
/**
* Definition for a binary tree node.
* 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:
TreeNode* traversal(vector<int>& nums,int left,int right)//构造二叉搜索树,前序遍历
{
//确定递归终止条件
//这里定义的是左闭右闭的区间,所以当区间 left > right的时候,就是空节点了。
if(left>right)return NULL;
int mid=(left+right)/2;
TreeNode *root=new TreeNode(nums[mid]);
//接着划分区间,root的左孩子接住下一层左区间的构造节点,右孩子接住下一层右区间构造的节点。
root->left=traversal(nums,left,mid-1);
root->right=traversal(nums,mid+1,right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
int left,right;
left=0;
right=nums.size()-1;
TreeNode* result=traversal(nums,left,right);
return result;
}
};
538.把二叉搜索树转换为累加树
本题也不难,在 求二叉搜索树的最小绝对差 和 众数 那两道题目 都讲过了 双指针法,思路是一样的。
https://programmercarl.com/0538.%E6%8A%8A%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91%E8%BD%AC%E6%8D%A2%E4%B8%BA%E7%B4%AF%E5%8A%A0%E6%A0%91.html
视频讲解:https://www.bilibili.com/video/BV1d44y1f7wP
/**
* Definition for a binary tree node.
* 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:
int pre=0;
void traversal(TreeNode* node)// 记录前一个节点的数值
{
if(node==NULL)return;
traversal(node->right);//右
node->val+=pre;//中
pre=node->val;
traversal(node->left);//左
}
TreeNode* convertBST(TreeNode* root) {
traversal(root);
return root;
}
};
总结篇
标签:right,TreeNode,val,int,随想录,二叉,搜索,root,left From: https://blog.csdn.net/2401_83080774/article/details/136711461https://programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E6%80%BB%E7%BB%93%E7%AF%87.html