代码随想录算法训练营Day18

669. 修剪二叉搜索树

力扣题目链接：. - 力扣（LeetCode）

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;
    }
}

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

力扣题目链接：. - 力扣（LeetCode）

循环不变量普遍用于二分查找和递归分割数组

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        int length=nums.length;
       return transform(nums,0,length);
    }
    public TreeNode transform(int[] nums,int left,int right){
        if(right-left<1){
            return null;
        }
        if(right-left==1){
            return new TreeNode(nums[left]);
        }
        int mid=left+(right-left)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=transform(nums,left,mid);
        root.right=transform(nums,mid+1,right);
        return root;
    }
}

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

力扣题目链接：. - 力扣（LeetCode）

逆中序遍历

class Solution {
    int sum;
    public TreeNode convertBST(TreeNode root) {
        sum=0;
        count(root);
        return root;
    }
    public void count(TreeNode root){
        if(root==null){
            return;
        }
        count(root.right);
        sum+=root.val;
        root.val=sum;
        count(root.left);
    }
}