#669 修剪二叉搜索树

给定一个二叉搜索树，同时给定最小边界L 和最大边界 R。通过修剪二叉搜索树，使得所有节点的值在[L, R]中 (R>=L) 。你可能需要改变树的根节点，所以结果应当返回修剪好的二叉搜索树的新的根节点。

#938 二叉搜索树的范围和

给定二叉搜索树的根结点root，返回 L 和 R（含）之间的所有结点的值的和。
二叉搜索树保证具有唯一的值。

解题思路：
这两道题其实解法很相似，充分利用递归来解决二叉搜索树的问题。

修剪二叉搜索树：对于某一个node，如果node<L，那么修剪后的二叉树就在这个node的右边；
如果node>R，那么修剪后的二叉树就在这个node的左边；
其他情况，就说明node在修剪后的二叉树中，也就只需对该node的children递归作相同处理。

def trim(node, L, R):
    if not node:
        return None
    if node.val < L:
        return trim(node.right, L, R)
    elif node.val > R:
        return trim(node.left, L, R)
    else:
        node.left = trim(node.left, L, R)
        node.right = trim(node.right, L, R)
        return node

二叉搜索树的范围和：有了上一题的经验，我们只需要在node处于[L, R]范围中时，加上该node的值。

def sum(node, L, R):
    if not node:
        return 0
    if node.val < L:
        return sum(node.right, L, R)
    elif node.val > R:
        return sum(node.left, L, R)
    else:
        return node.val + sum(node.left, L, R) + sum(node.right, L, R)

时间复杂度和空间复杂度均为O(N)，其中N为二叉搜索树的节点数，因为最多会遍历每一个节点。