原题链接在这里：

题目：

Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.

Example 1:

Input:     1   / \  0   2  L = 1  R = 2Output:     1      \       2

Example 2:

Input:     3   / \  0   4   \    2   /  1  L = 1  R = 3Output:       3     /    2     / 1

题解：

在[L, R]区间外trim. 

Recursive call, stop condition, root == null, return root.

如果root.val 小于 L, 则root右侧有可能在区间内，返回trim后的 root.right. 

如果root.val 大于 R, 则root左侧有可能在区间内，返回trim后的root.left.

如果root.val在区间内, 则对左右两侧分别trim后return root.

Time Complexity: O(n), n 是node数.

Space: O(logn), stack space.

AC Java:

1 /** 2  * Definition for a binary tree node. 3  * public class TreeNode { 4  *     int val; 5  *     TreeNode left; 6  *     TreeNode right; 7  *     TreeNode(int x) { val = x; } 8  * } 9  */10 class Solution {11     public TreeNode trimBST(TreeNode root, int L, int R) {12         if(root == null){13             return root;14         }15         16         if(root.val < L){17             return trimBST(root.right, L, R);18         }19         if(root.val > R){20             return trimBST(root.left, L, R);21         }22         23         root.left = trimBST(root.left, L, R);24         root.right = trimBST(root.right, L, R);25         26         return root;27     }28 }