day23 打卡669. 修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

1.迭代法

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.将有序数组转换为二叉搜索树

108题目链接

1.递归法

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

    public TreeNode sortedArrayToBST(int[] nums, int start, int end) {
        if (start>=end) return null;
        if (end-start==1) return new TreeNode(nums[start]);
        int mid = start + (end-start)/2;
        TreeNode cur = new TreeNode(nums[mid]);
        cur.left = sortedArrayToBST(nums, start, mid);
        cur.right = sortedArrayToBST(nums, mid+1, end);
        return cur;
    }
}

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

538题目链接

1.递归法

class Solution {
    int sum = 0;

    public TreeNode convertBST(TreeNode root) {
        if (root==null) return null;
        convertBST1(root);
        return root;
    }

    public void convertBST1(TreeNode cur) {
        if (cur == null) return;
        // 右
        convertBST(cur.right);

        // 中
        sum += cur.val;
        cur.val = sum;

        // 左
        convertBST(cur.left);
    }
}