题目：
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, 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* trimBST(TreeNode* root, int low, int high) {
//递归
//终止条件
if (root == nullptr) return nullptr;
//处理过程
//这里自己写出bug了，其实想到了问题出在哪里，删除节点后需要保证新节点也在范围内，所以需要递归
if (root -> val < low) {
//返回右子树
//错误写法
// return root -> right;
return trimBST(root -> right, low, high);
}
if (root -> val > high) {
//错误写法
// return root -> left;
return trimBST(root -> left, low, high);
}
//递归过程
root -> left = trimBST(root -> left, low, high);
root -> right = trimBST(root -> right, low, high);
return root;
}
};
// class Solution {
// public:
// TreeNode* trimBST(TreeNode* root, int low, int high) {
// if (root == nullptr) return nullptr;
// 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;
// }
// };
题目：
给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。
高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 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 mid = left + (right - left) / 2;
TreeNode* node = new TreeNode(nums[mid]);
//左闭右闭的区间
node -> left = traversal(nums, left, mid - 1);
node -> right = traversal(nums, mid + 1, right);
return node;
}
TreeNode* sortedArrayToBST(vector<int>& nums) {
TreeNode* root = traversal(nums, 0, nums.size() - 1);
return root;
}
};
题目：
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.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 {
public:
int pre = 0;
//核心思路在于 从大往小开始遍历，每遍历到一个节点，把前面比当前节点大的值都累加到当前节点上，所以考虑记录之前遍历的节点的累加和
//二叉搜索树中序遍历，但是要右中左就是从大往小遍历， 然后不需要改变树的指向结构，只改变数值，所以递归函数不需要返回值
void traversal(TreeNode* cur) {
//终止条件
if (cur == nullptr) return ;
//递归内容
traversal(cur -> right);
//处理 改变当前节点值
cur -> val += pre;
//第一遍写忘记改变pre值了
pre = cur -> val;
traversal(cur -> left);
return ;
}
TreeNode* convertBST(TreeNode* root) {
//初始化累加值
pre = 0;
traversal(root);
return root;
}
};