[代码随想录Day21打卡] 669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树总结篇

669. 修剪二叉搜索树

给定一个二叉搜索树root，给定一个范围[low, high]，修剪二叉搜索树，使修建后的二叉搜索树的值的范围在[low, high]内。
思想：当前节点的值和给定的范围之间的关系，如果当前节点的值大于high那么就是递归遍历它的左子树(因为它的左子树中的值小于该节点的值，可能存在符合范围的节点)，如果当前节点的值小于low，那么递归遍历它的右子树（因为他的右子树中的值大于该节点的值，可能存在符合范围的节点）。

递归三部曲
确定递归函数的参数和返回值：参数就是root, low, high，返回值类型是TreeNode*，返回的给定范围的修建后的二叉树的根节点。
确定终止条件：
如果root==NULL return NULL;
确定单层递归的逻辑：
中：如果当前节点的值小于low，返回traversal(root->right, low, right)，如果当前节点的值大于high，返回traversal(root->left,low, high)；
左：root-> left = traversal(root->left, low, high)
右：root->right = traversal(root->right, low, high)
return root；

在这里插入图片描述
下面是C++, JAVA, Python代码。

/*** 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==NULL) 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;}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode trimBST(TreeNode root, int low, int high) {if(root==null) 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;}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def trimBST(self, root, low, high):""":type root: Optional[TreeNode]:type low: int:type high: int:rtype: Optional[TreeNode]"""if root==None:return Noneif root.val < low:return self.trimBST(root.right, low, high)if root.val > high:return self.trimBST(root.left, low, high)root.left = self.trimBST(root.left, low, high)root.right = self.trimBST(root.right, low, high)return root

参考文章

https://programmercarl.com/0669.%E4%BF%AE%E5%89%AA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE

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

有点类似于前面的构造最大二叉树。
构造二叉树的遍历方式一般选择前序遍历。
思想：选取中间值构造根节点，选取左区间构造左子树，选取右区间构造右子树。
注意：区间定义要统一。这里使用左闭右闭。（也可以左闭右开）
递归三部曲
确定递归函数的参数和返回值：参数就是nums,left,right，返回值类型是TreeNode*，返回的数组nums的[left, right]区间内构造的二叉树的根节点。
确定终止条件：
如果left>right（与区间定义有关），return NULL; 如果left>right没有值无法构造节点就返回空。
确定单层递归的逻辑：
中：确定区间的中间位置mid = (left+right)/2，构造新的根节点root = new TreeNode(nums[mid])
左：root->left = traversal(nums, left, mid-1）//这个还是和区间定义有关我们是左闭右闭所以左区间就是left,mid-1不包括mid
右：root->right = traversal(nums, mid+1, right) //右区间不包括mid所以从mid+1开始
return root；
下面是C++, JAVA, Python代码。

/*** 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 NULL;int mid = (left + right)/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) {return traversal(nums, 0, nums.size()-1);}
};

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public TreeNode traversal(int[] nums, int left, int right){if(left>right) return null;int mid = (left+right)/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(int[] nums) {return traversal(nums, 0, nums.length-1);}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def sortedArrayToBST(self, nums):""":type nums: List[int]:rtype: Optional[TreeNode]"""# if len(nums) <=0:#     return None# mid = len(nums)/2# root = TreeNode(nums[mid])# root.left = self.sortedArrayToBST(nums[:mid])# root.right = self.sortedArrayToBST(nums[mid+1:])# return rootreturn self.traversal(nums, 0, len(nums)-1)def traversal(self, nums, left, right):if left > right:return Nonemid = (left+right)/2root = TreeNode(nums[mid])root.left = self.traversal(nums, left, mid-1)root.right = self.traversal(nums, mid+1, right)return root

参考文章

https://programmercarl.com/0108.%E5%B0%86%E6%9C%89%E5%BA%8F%E6%95%B0%E7%BB%84%E8%BD%AC%E6%8D%A2%E4%B8%BA%E4%BA%8C%E5%8F%89%E6%90%9C%E7%B4%A2%E6%A0%91.html

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

秒了。
这个是中序倒过来，遍历顺序就是右中左。
设定一个全局变量保存前一个节点的值就可以了。
递归三部曲
确定递归函数的参数和返回值：参数是root，返回值是变成累加树的二叉树的根节点。
确定终止条件：
如果root==NULL return;
确定单层递归的逻辑：
右：root->right = traversal(root->right)
中： root->val += pre; pre = root->val;//更新pre使他一直保存着前一个节点的值
左：root->left= traversal(root->left)
return root；

下面是C++, JAVA, Python代码。

/*** 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 {int count = 0;
public:TreeNode* convertBST(TreeNode* root) {if(root==NULL) return NULL;root->right = convertBST(root->right);root->val = root->val+count;count = root->val;root->left = convertBST(root->left);return root;}
};// class Solution {
//     // int count = 0;
//     TreeNode* pre;
// public:
//     TreeNode* convertBST(TreeNode* root) {
//         if(root==NULL) return NULL;
//         root->right = convertBST(root->right);
//         if(pre==NULL){
//             pre = root;
//         }else{
//             root->val += pre->val;
//             pre = root;
//         }
//         root->left = convertBST(root->left);
//         return root;
//     }
// };

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {int pre = 0;public TreeNode convertBST(TreeNode root) {if(root==null) return null;root.right = convertBST(root.right);        root.val += pre;pre = root.val;root.left = convertBST(root.left);return root;}
}

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):def __init__(self):self.pre = 0def convertBST(self, root):""":type root: Optional[TreeNode]:rtype: Optional[TreeNode]"""if root == None:return Noneroot.right = self.convertBST(root.right)root.val = root.val + self.preself.pre = root.valroot.left = self.convertBST(root.left)return root