代码随想录算法训练营day23|669.修剪二叉搜索树、108.将有序数组转换为二叉搜索树、538.把二叉搜索树转换为累加树

669.修剪二叉搜索树

这道题目需要考虑当前节点是否在[low,high]之间，
因为是平衡二叉树，
所以当当前节点值小于low时，那么其左节点肯定更小，因此删除该节点的方式是给root节点返回其右节点的递归，注意：这里不是直接返回右节点，是因为在右子树中也有可能存在不满足条件的节点，需要继续递归排查；
当当前节点值大于high时，那么其右节点肯定更大，因此删除该节点的方式是给root节点返回其左节点的递归。
如果root.val符合在[low,high]的区间内，其左右节点承接左右节点的返回值即可。
最终返回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;else if(root.val < low) return trimBST(root.right,low,high);else 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;}
}

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

每次取中间索引的值构造节点，利用递归构造平衡二叉搜索树。
要注意限定左右指针的大小条件：if(right < left) return null;

/*** 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 sortedArrayToBST(int[] nums) { if(nums.length == 0) return null;return build(nums,0,nums.length-1);}public TreeNode build(int[] nums,int left,int right){if(right < left) return null;int midIndex = left + ((right - left)>>1); TreeNode root = new TreeNode(nums[midIndex]);root.left = build(nums,left,midIndex-1);root.right = build(nums,midIndex+1,right);return root;}
}

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

/*** 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) {plusProcess(root);return root;}public void plusProcess(TreeNode root){//右中左遍历//终止条件if(root == null) return;//右plusProcess(root.right);//中pre += root.val;root.val = pre;//每次改变root节点的值//左plusProcess(root.left);}
}