669. Trim a Binary Search Tree 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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);
        }
        if (root.val > high) {
            // 当前 root 节点和右子树都应该丢弃
            return trimBST(root.left, low, high);
        }

        root.left = trimBST(root.left, low, high);
        root.right = trimBST(root.right, low, high);
        return root;
    }
}

References

669. Trim a Binary Search Tree