题目和思路

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 = 2

Output: 
    1
      \
       2
Example 2:
Input: 
    3
   / \
  0   4
   \
    2
   /
  1

  L = 1
  R = 3

Output: 
      3
     / 
   2   
  /
 1

递归修剪，比L小的则继续修剪当前节点的右子树；比R大的则继续修剪当前节点的左子树；若是在范围内，则将左子树设为递归左子树的返回值，右子树设为递归右子树的返回值。

代码

package tree;

/**
 * Created by liqiushi on 2018/1/31.
 */
public class TrimABinarySearchTree {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if(root == null){
            return root;
        }
        if(root.val < L ){
            return trimBST( root.right,  L,  R);
        }else if(root.val > R){
            return trimBST( root.left,  L,  R);
        }
        root.left = trimBST( root.left,  L,  R);
        root.right = trimBST( root.right,  L,  R);
        return root;
    }
}