669. 修剪二叉搜索树

669. 修剪二叉搜索树 - 力扣（LeetCode）
本题主要分为3种情况，如果root.val<low，那么去右子树修剪，此时不能直接返回右子树，因为右子树可能有不符合规则的，如果root.val>high，同理去左子树修剪，如果在low和high内，那么保留root，并赋予root的左右子树

class Solution {
    public TreeNode trimBST(TreeNode root, int low, int high) {
        if (root == null) return null;
        if (root.val < low) {
            // 不保留root，返回修剪后的右节点
            return trimBST(root.right, low, high);
        } else if (root.val > high) {
            return trimBST(root.left, low, high);
        } else {
            // 保留root
            root.left = trimBST(root.left, low, high);
            root.right = trimBST(root.right, low, high);
            return root;
        }
    }
}

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

108. 将有序数组转换为二叉搜索树 - 力扣（LeetCode）
本题可以分为左闭右开和左闭右闭，将中间的值作为根节点，左边作为左子树，右边作为右子树

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

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

538. 把二叉搜索树转换为累加树 - 力扣（LeetCode）
将节点的值换成大于等于该值的节点的和，按照右中左的中序遍历的方法，用sum记录总和

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