文档讲解：修剪二叉搜索树??将有序数组转换为二叉搜索树??把二叉搜索树转换为累加树
题目链接：https://leetcode.cn/problems/trim-a-binary-search-tree/description/
思路：
? ? ? ?要修剪，我们就要遍历这些点，判断其值是否在范围内，很明显，最简单的想法是用递归来做，同时终止条件为遍历到空节点，这时候返回即可。也不需要修剪，因为修剪在我们判断值的时候去做。
? ? ? ? 接下来我们确定什么时候需要修剪以及如何修剪：
? ? ? ? 1.如果当前节点的元素小于low的数值，那么应该递归右子树，并返回右子树符合条件的头结点。
? ? ? ? 2.如果当前节点的元素大于high的数值，那么应该递归左子树，并返回左子树符合条件的头结点。
? ? ? ? 3.接下来要将下一层处理完左子树的结果赋给cur->left，处理完右子树的结果赋给cur->right。返回当前节点cur即可。
核心代码：
/**
* 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) 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;
}
};题目链接：https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree/description/
思路：
? ? ? ? 本题目要求我们将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
? ? ? ? 因为他保证数组内数值有序了，所以我们其实只需要分割区间就可以了，和前面很多道题建树很相似，而且建树也很简单，因为中间位置的节点就是根节点，每次取中间位置做根，左右分割去构建左右子树，构建到底层后进行回溯，回溯每个根节点，然后每层根据回溯上来的左右子树根节点给当前节点的left和right赋值即可。
核心代码：
/**
* 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 {
private:
TreeNode* traversal(vector<int>& nums, int left, int right) {
if (left > right) return nullptr;
int mid = left + ((right - left) / 2);
TreeNode* root = new TreeNode(nums[mid]);
root->left = traversal(nums, left, mid - 1);
root->right = traversal(nums, mid + 1, right);
return root;
}
public:
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};题目链接：https://leetcode.cn/problems/convert-bst-to-greater-tree/
思路：
? ? ? ? 这题的意思是，把原本的节点值val，换为树中所有大于等于val的节点值之和。
? ? ? ? 我们首先要意识到一件事，这是一株二叉搜索树。也就是说，树上的节点永远满足左<根<右。所以我们要做的就是从右向左来加，右的值加到中上，再把中的值加到左上，就加完了。
? ? ? ? 那右中左是什么呢？是中序遍历的反转对吧。那我们知道，中序遍历的迭代法用栈来维护，刚好就是顺序反着来得。所以这是一道中序遍历的模板题，不过每次要记录上一个节点的值，也就是前面的累加值，加到当前节点上，同时更新记录值即可。遍历结束后每个点的累加也就结束了，这道题也就做完了。
核心代码：
/**
* 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 {
private:
int pre;
void traversal(TreeNode* root) {
stack<TreeNode*> st;
TreeNode* cur=root;
while(cur||!st.empty()){
if(cur){
st.push(cur);
cur=cur->right;
}else{
cur=st.top();
st.pop();
cur->val+=pre;
pre=cur->val;
cur=cur->left;
}
}
}
public:
TreeNode* convertBST(TreeNode* root) {
pre=0;
traversal(root);
return root;
}
};????????今日学习时长3h，题目不算难，没来的及看其他解法，这几天有一点忙，要到处跑，还有其他任务，说实话累坏了，头疼的要命，等周末有时间再总结吧。