day23

1、669 修剪二叉搜索树

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

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

1、代码实现1

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        if(nums.length == 0){
            return null;
        }
        int midIndex =  nums.length / 2 ;
        TreeNode root = new TreeNode(nums[midIndex]);

        int[] leftNums = Arrays.copyOfRange(nums,0,midIndex);
        int[] rightNums = Arrays.copyOfRange(nums,midIndex+1, nums.length);
        
        root.left = sortedArrayToBST(leftNums);
        root.right = sortedArrayToBST(rightNums);
        
        return root;
    }
}

2、代码实现2

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return traversal(nums, 0, nums.length);
    }

    public TreeNode traversal(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);
        root.right = traversal(nums, mid+1, right);
        return root;
    }
}

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

class Solution {
    int preVal = 0;

    public TreeNode convertBST(TreeNode root) {
        traversal(root);
        return root;
    }

    public void traversal(TreeNode cur) {
        if(cur==null) {
            return;
        }
        //右
        traversal(cur.right);
        //中
        cur.val += preVal;
        preVal = cur.val;
        //左
        traversal(cur.left);
    }
}