修剪二叉搜索树

给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树 不应该 改变保留在树中的元素的相对结构 (即，如果没有被移除，原有的父代子代关系都应当保留)。可以证明，存在 唯一的答案 。

所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。

示例 1：
输入：root = [1,0,2], low = 1, high = 2
输出：[1,null,2]
示例 2：
输入：root = [3,0,4,null,2,null,null,1], low = 1, high = 3
输出：[3,2,null,1]
提示：

树中节点数在范围 [1, 104] 内
0 <= Node.val <= 104
树中每个节点的值都是唯一的
题目数据保证输入是一棵有效的二叉搜索树
0 <= low <= high <= 104

我们在剪枝的时候，要考虑这个节点数字的大小，如果值小于low的话，那我们就先递归，再return他的右孩子；如果大于high的话，就先递归，再返回他的左孩子（先递归是因为左/右孩子中不一定完全都是在范围的值）

然后缔造联系即可。

/*** 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(TreeNode* cur, int low, int high){if(cur==nullptr)return nullptr;if(cur->val<low){TreeNode* right = traversal(cur->right,low,high);return right;}if(cur->val>high){TreeNode* left = traversal(cur->left,low,high);return left;}cur->left = traversal(cur->left,low,high);cur->right = traversal(cur->right,low,high);return cur;}TreeNode* trimBST(TreeNode* root, int low, int high) {return traversal(root,low,high);}
};

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

给你一个整数数组 nums ，其中元素已经按升序排列，请你将其转换为一棵平衡二叉搜索树。

示例 1：
输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：
示例 2：
输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。
提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

这个题就是每次找到区间的中间值放到节点上，不断进行划分。

注意：

1.在找中间值时，要用 left+(right-left)/2这种方式，就不会出现溢出的情况。

 cur->left = traversal(nums,0,temp-1);cur->right = traversal(nums,temp+1,nums.size()-1);

我写的时候写成了这样，这只能保证二叉树最左侧节点和最右侧节点是正常的，而中间的节点就会出问题。

正确代码如下：

/*** 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){if(left>right) return nullptr;int  temp = left + ((right - left) / 2);TreeNode* cur = new TreeNode(nums[temp]);cur->left = traversal(nums,left,temp-1);cur->right = traversal(nums,temp+1,right);return cur;}TreeNode* sortedArrayToBST(vector<int>& nums) {return traversal(nums,0,nums.size()-1);}
};

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

给出二叉搜索树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。

提醒一下，二叉搜索树满足下列约束条件：

节点的左子树仅包含键小于节点键的节点。
节点的右子树仅包含键大于节点键的节点。
左右子树也必须是二叉搜索树。

注意：本题和 1038: 1038. 从二叉搜索树到更大和树 - 力扣（LeetCode）相同

示例 1：
输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
示例 2：
输入：root = [0,null,1]
输出：[1,null,1]
示例 3：
输入：root = [1,0,2]
输出：[3,3,2]
示例 4：
输入：root = [3,2,4,1]
输出：[7,9,4,10]
提示：

树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。

这道题注意：因为只需要修改每个位置的值，所以递归是void类型的。

累加数：其实这就是一棵树，大家可能看起来有点别扭，换一个角度来看，这就是一个有序数组[2, 5, 13]，求从后到前的累加数组，也就是[20, 18, 13]，是不是感觉这就简单了。

也就是我们需要用右中左的顺序即可完成。

/*** 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* cur){if(cur==nullptr)return ;traversal(cur->right);cur->val += pre;pre = cur->val;traversal(cur->left);}TreeNode* convertBST(TreeNode* root) {pre = 0;traversal(root);return root;}
};