二叉树刷题篇（完） 二叉搜索树的修剪、构造与转换
669. 修剪二叉搜索树
给你二叉搜索树的根节点 root ，同时给定最小边界low 和最大边界 high。通过修剪二叉搜索树，使得所有节点的值在[low, high]中。修剪树不应该改变保留在树中的元素的相对结构（即，如果没有被移除，原有的父代子代关系都应当保留）。 可以证明，存在唯一的答案。所以结果应当返回修剪好的二叉搜索树的新的根节点。注意，根节点可能会根据给定的边界发生改变。
https://leetcode-cn.com/problems/trim-a-binary-search-tree/
class Solution {public:TreeNode* trimBST(TreeNode* root, int low, int high) {if(root==NULL) return NULL;if(root->val<low){TreeNode* right=trimBST(root->right, low, high);return right;}if(root->val>high){TreeNode* left=trimBST(root->left, low, high);return left;}root->left=trimBST(root->left,low,high);root->right=trimBST(root->right,low,high);return root;}};
108. 将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
https://leetcode-cn.com/problems/convert-sorted-array-to-binary-search-tree/
class Solution {private:TreeNode* traversal(vector<int>& nums, int left, int right) {if (left > right) return NULL;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;}};
538. 把二叉搜索树转换为累加树
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
https://leetcode-cn.com/problems/convert-bst-to-greater-tree
class Solution {public:void traversal(TreeNode* cur,int &sum){if(cur==NULL) return;traversal(cur->right,sum);sum+=cur->val;cur->val=sum;traversal(cur->left,sum);}TreeNode* convertBST(TreeNode* root) {int sum=0;traversal(root,sum);return root;}};