代码随想录算法训练营第二十一天|LeetCode669. 修剪二叉搜索树，LeetCode108. 将有序数组转换为二叉搜索树，LeetCode538. 把二叉搜索树转换为累加树

LeetCode669. 修剪二叉搜索树

题目链接：669. 修剪二叉搜索树 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：你修剪的方式不对，我来给你纠正一下！| LeetCode：669. 修剪二叉搜索树_哔哩哔哩_bilibili

思路：如果节点的值比low小，就说明需要去掉这个节点，然后这个节点的左孩子也不用在考虑了，所以此处应该直接返回往右遍历的结果，如果比high大，同理，应该返回这个节点往左遍历的结果，如果在low和high之间，应该要保留，所以直接往左和右遍历就好，再返回这个节点。

代码：

class Solution {
public:
TreeNode* trimBST(TreeNode* root, int low, int high) {
if(root==NULL){
return NULL;
}
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;
}
};

LeetCode108. 将有序数组转换为二叉搜索树

题目链接：108. 将有序数组转换为二叉搜索树 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：构造平衡二叉搜索树！| LeetCode：108.将有序数组转换为二叉搜索树_哔哩哔哩_bilibili

思路：这道题比较简单，有点类似于二分查找，函数的参数是数组和范围的左端和右端，初始的left和right就是数组的两端，然后每次选取这个范围的中间值mid为root节点，然后往左孩子遍历的数组范围就变成了left和mid-1，右孩子遍历的数组范围是mid+1和right。

代码：

class Solution {
public:
TreeNode* traversal(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=traversal(nums,left,mid-1);
root->right=traversal(nums,mid+1,right);
return root;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
return traversal(nums,0,nums.size()-1);
}
};

LeetCode538. 把二叉搜索树转换为累加树

题目链接：538. 把二叉搜索树转换为累加树 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：普大喜奔！二叉树章节已全部更完啦！| LeetCode：538.把二叉搜索树转换为累加树_哔哩哔哩_bilibili

思路：这道题按照反向中序的方向遍历，也就是右中左，只要先定义一个变量保存前一个节点的值，然后再把前一个节点的值加到当前节点上，然后再让这个变量保存当前节点的值。

代码：

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;
}
};