Day23 二叉树09

 669. 修剪二叉搜索树 

题目链接：669. 修剪二叉搜索树 - 力扣（LeetCode）

思路：节点值不在区间式，返回的不是子节点，而是递归调度,而且根据二叉搜索树特征，该节点小于key则所有左子树都小于key，右子树同理。

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

思路：从中间节点开始

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

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

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

    public void convertBST1(TreeNode root){
        if(root == null) return;
        convertBST1(root.right);
        pre = pre + root.val;
        root.val = pre;
        convertBST1(root.left);
        return;
    }
}