題目和思路

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小的則繼續(xù)修剪當前節(jié)點的右子樹；比R大的則繼續(xù)修剪當前節(jié)點的左子樹；若是在范圍內，則將左子樹設為遞歸左子樹的返回值，右子樹設為遞歸右子樹的返回值。

代碼

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;
    }
}