代码随想录 第23天 | 669. 修剪二叉搜索树 ● 108.将有序数组转换为二叉搜索树 ● 538.把二叉搜索树转换为累加树 ● 总结篇

leetcode：669. 修剪二叉搜索树 - 力扣（LeetCode）

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        //和删除差不多，怕删除的节点的左右孩子节点有符合范围的，所以要每次判断一下，如果有不符合要求的就直接返回上一个节点。
        if( root == null) return root;
        //删除节点，判断该节点右孩子有没有符合题目范围的
        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;

    }
}

 leetcode：108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）

class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {

        return gettree(nums,0,nums.length - 1);
    }
    public TreeNode gettree(int[] nums,int left,int right){
        //判断越界
        if(left > right) return null;
        int mid = (left + right)/2;
        //将中间节点作为根节点
        TreeNode node = new TreeNode(nums[mid]);
        //将数组区分成左右节点。
        node.left = gettree(nums,left,mid-1);
        node.right = gettree(nums,mid+1,right);
        return node;


    }
}

leetcode：538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）

class Solution {
    //初始0
    TreeNode pre = new TreeNode(0);
    public TreeNode convertBST(TreeNode root) {
    //终止条件
        if( root == null) return null;
        //因为是后续遍历的倒序，所以是右中左
        //右
        root.right = convertBST(root.right);
        //中，将累加的值赋给root
        pre.val += root.val;
        root.val = pre.val;
        //左
        root.left = convertBST(root.left);
        return root;
    }
}