今日总结：

1、修剪二叉搜索树（重点思考如何修剪）

（1）递归的返回值是什么？（与插入、删除一样）

（2）递归的单层逻辑一定要缕清（3中情况讨论）

2、将有序数组转化为二叉搜索树(简单)

3、把二叉搜索树转换为累加树

需要思考出所谓的累加树就是从右下角开始，逆中序遍历，将前一个值加到当前值中，所以与中序遍历对当前值操作一样，需要使用一个全局变量记录前一个节点。

修剪二叉搜索树

题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）

整体思路：

思路1：笨方法（不行，因为不能改变树的原本结构）

1、将二叉搜索树变化为有序数组（中序遍历）

2、将有序数组减枝

3、将数组排列成二叉搜索树

思路2：递归

本质上就是判断当前节点的值是不是在目标区间中：

1、小于目标区间：要删除当前节点，当前节点的左子树一定小于目标区间，去递归当前节点的右子树，寻找右子树是不是存在符合目标区间的节点，将该节点作为当前节点返回

2、大于目标区间：要删除当前节点，当前节点的右子树一定大于目标区间，去递归当前节点的左子树，寻找左子树是不是存在符合目标区间的节点，将该节点作为当前节点返回

3、在目标区间中：不能直接返回当前节点，因为不知道当前节点的左右子树中是不是存在不满足区间的节点，所以需要递归左右子树，更新当前节点的左右子节点后再返回当前节点。

思路2整体代码

/*** 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* digui(TreeNode* cur, int low, int high){//停止条件：空节点if(cur==nullptr)return nullptr;//单程递归逻辑：上边已经写出了if(cur->val<low){return digui(cur->right,low,high);}else if(cur->val>high){return digui(cur->left,low,high);}//在区间内,需要判断左右子树是不是符合条件cur->left = digui(cur->left,low,high);cur->right =digui(cur->right,low,high);return cur;}TreeNode* trimBST(TreeNode* root, int low, int high) {return digui(root,low,high);}
};

将有序数组转化为二叉搜索树

题目链接：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

整体思路：

二分法将数组分成两部分，递归构造

返回值：

当前节点

输入值：

数组

停止：

数组空

单层逻辑：

1、寻找数组中间值

2、分成两个数组

3、构建一个节点，值为中间值

4、左子节点递归

5、右子节点递归

6、返回当前节点

整体代码：

/*** 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* digui(vector<int>& nums){if(nums.size()==0)return nullptr;//中间值int mid = nums.size()/2;TreeNode* cur = new TreeNode(nums[mid]);vector <int>res_left (nums.begin(),nums.begin()+mid);vector <int>res_right (nums.begin()+mid+1,nums.end());cur->left = digui(res_left);cur->right =digui(res_right);return cur;}TreeNode* sortedArrayToBST(vector<int>& nums) {return digui(nums);}
};

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

题目链接：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

整体思路：

累加树：当前节点的值加上比当前节点值大的节点的所有值构建的树

二叉搜索树：当前节点左子树的值全部比当前节点的值小；当前节点的右子树的值全部比当前节点的值大。

分析可知二叉搜索树与累加树的关系：当前节点的值加上当前节点的右子树的值之和

从右下开始遍历（逆中序遍历），而不是从左下开始（中序遍历），每次遍历将当前节点的值变为前边所有值之和。

1、递归的返回值，输入值

返回值：无需返回值

输入值：当前节点

2、递归的停止条件：

遇到空节点

3、单层递归逻辑

与中序遍历相反，先遍历右子节点、再对当前节点做加和，再遍历左子节点。

因为是单纯的中序遍历，修改当前节点问题，需要知道前一个节点的值，所以需要使用一个全局变量去记录前一个节点

整体代码：

/*** 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* res= nullptr;//返回值：更新的当前节点//输入值：当前节点void digui(TreeNode* cur){   //空节点停止if(cur==nullptr){return ;}//单层递归，逆中序遍历digui(cur->right);if(res!=nullptr)cur->val =cur->val+ res->val;res = cur;digui(cur->left);}TreeNode* convertBST(TreeNode* root) {digui(root);return root;}
};