代码随想录day20 | leetcode 669.修剪二叉搜索树 108.将有序数组转换为二叉搜索树 538.把二叉搜索树转换为累加树

修剪二叉搜索树

以下是修剪二叉搜索树的步骤：

1. 如果当前节点为空，直接返回空。
2. 如果当前节点的值小于L，那么它和它的左子树都不在范围内，应该修剪掉。因此，返回修剪其右子树的结果，右子树中可能含有符合条件的结果，对其修剪。
3. 如果当前节点的值大于R，那么它和它的右子树都不在范围内，应该修剪掉。因此，返回修剪其左子树的结果。
4. 如果当前节点的值在L和R之间，那么保留当前节点，并递归修剪其左右子树。

public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null){
            return null;
        }
        if (root.val<low){
            TreeNode node = trimBST(root.right,low,high);//修剪左孩子的右子树
            return node;
        }
        if (root.val>high){
            TreeNode node = trimBST(root.left,low,high);
            return node;
        }
        root.left = trimBST(root.left,low,high);
        root.right = trimBST(root.right,low,high);
        return root;


    }

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

题目：给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 平衡 二叉搜索树。
构造二叉树：为了保证平衡，使左区间的节点数与右区间的节点数相同，从中间选取根节点，切割数组使用左闭右闭，递归重复步骤。

 public TreeNode sortedArrayToBST(int[] nums) {
        TreeNode root = PF(nums,0,nums.length-1);
        return root;
    }


    public TreeNode PF(int[] nums,int left, int right){
        TreeNode root;
        if (left> right){//当left = right 时数组中只有一个元素，也需要做处理。
            return null;
        }
        int mid = (left + right)/2;
        root = new TreeNode(nums[mid]);
        root.left = PF(nums,left,mid-1);
        root.right = PF(nums,mid+1,right);
        return root;
    }

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

中序遍历：从小到大。累加，从大到小。
从树中可以看出累加的顺序是右中左，所以我们需要反中序遍历这个二叉树，然后顺序累加就可以了

int per = 0;//如果 per 是局部变量，那么它在每次调用时都会被重置，这样就无法实现累加的效果。
    public TreeNode convertBST(TreeNode root) {
          dft(root);
        return root;
    }
    public void dft(TreeNode root){
       
        if (root==null){
            return;
        }
        dft(root.right);
        per += root.val;
        root.val = per;
        dft(root.left);
    }