Day18 二叉树part08| LeetCode 669. 修剪二叉搜索树 ， 108.将有序数组转换为二叉搜索树，538.把二叉搜索树转换为累加树

669. 修剪二叉搜索树

669. 修剪二叉搜索树

 class Solution {
        public TreeNode trimBST(TreeNode root, int low, int high) {
           if(root==null) return null;
            //处理节点值<low 的情况：当前节点及其左子树的所有节点都不在范围内，继续在其右子树上修剪
           if(root.val<low)
           {
               TreeNode right=trimBST(root.right,low,high);
               return right;
           }
            //处理节点值>high 的情况：当前节点及其右子树的所有节点都不在范围内，继续在其左子树上修剪
           if(root.val>high)
           {
               TreeNode left=trimBST(root.left,low,high);
               return left;
           }
            //当前节点的值在范围内，保留当前节点，并递归修剪其左子树和右子树
           root.left=trimBST(root.left,low,high);
           root.right=trimBST(root.right, low,high);
           return root;

        }
    }

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

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

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

            TreeNode root=traserval(nums,0,nums.length-1);
            return  root;
        }
        TreeNode traserval(int[] nums,int left,int right)//左闭右闭
        {
            //终止条件
            if(left>right)
            {
                return null;

            }
            //单层逻辑
             int mid=(left+right)/2;
            TreeNode root=new TreeNode(nums[mid]);
           root.left=traserval(nums,left,mid-1);
           root.right=traserval(nums,mid+1,right);


            return root;
        }
    }

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

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

class Solution {
       int pre=0;
        public TreeNode convertBST(TreeNode root) {
            traversal(root);
            return root;

        }
        void traversal(TreeNode node)
        {
            if(node==null) return;
            //右中左

            traversal(node.right);
            node.val=pre+node.val;
            pre=node.val;
            traversal(node.left);
            

        }
    }