代码随想录第二十三天 ｜ 二叉树终章

今天终于是 二叉树的最后一章了，三道题，加油！

669. 修剪二叉搜索树

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if(root == null){
            return root;
        }
        
        root.left = trimBST(root.left, low, high);

        
        
        root.right = trimBST(root.right, low, high);
        
        if(root.val < low ){
            return root.right;
        }
        if(root.val > high){
            return root.left;
        }
        return root;
    }
}

只保留处于high 和low 中间的树部分

108. 将有序数组转化为二叉树

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

二分即可

538. 将二叉搜索树转为累加树

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

从大到小再累加

终于做完二叉树了，对递归法对认知提升了不少，明天开始新的篇章