Trim a Binary Search Tree

给一个BST, 然后给一个L和R两个整数, 给BST剪枝(trim), 问剪枝后的树. 这个题很有意思, 首先要理解剪枝这个操作, 仅仅是针对当前node的. 而对于node的子树,需要重新判断, 那么这个题就是一个子问题划分的题, 我们要通过递归不断把问题分解. 通过观察example, 我们可以看出, node.val如果大于R, 那么node的右边的子树都大于R, 那么都应该剪掉, 所以返回node的左边, 并且继续子问题探索. 同理对node.val小于R的情况. 如果node.val在L和R之间, 那么我们只需要继续分开讨论左边和右边子问题即可.

class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root == null)
            return null;
        if(root.val < L)
            return trimBST(root.right, L, R);
        else if(root.val > R)
            return trimBST(root.left, L, R);
        else {
            root.left = trimBST(root.left, L, R);
            root.right = trimBST(root.right, L, R);
            return root;
        }
    }
}