TrimABinarySearchTree [source code]

public class TrimABinarySearchTree {
static
/******************************************************************************/
class Solution {
    public TreeNode trimBST(TreeNode root, int L, int R) {
        if (root == null)
            return null;
        if (root.left == null && root.right == null) {
            if (root.val >= L && root.val <= R)
                return root;
            else
                return null;
        }
        TreeNode left = trimBST(root.left, L, R), right = trimBST(root.right, L, R);
        TreeNode res;
        if (root.val >= L && root.val <= R) {
            res = new TreeNode(root.val);
            res.left = left;
            res.right = right;
        } else {
            if (right == null)
                return left;
            else {
                TreeNode cur = right;
                while (cur.left != null)
                    cur = cur.left;
                cur.left = left;
                res = right;
            }
        }
        return res;
    }
}
/******************************************************************************/

    public static void main(String[] args) {
        TrimABinarySearchTree.Solution tester = new TrimABinarySearchTree.Solution();
    }
}

刚开始思考人逻辑, 所以想要直接用iteration做, 毕竟BST本身iteration也简单一些; 但是后来思考了一下, 为了处理root的问题, 最后还是要用recursion来做;

大概写了一下最后居然直接一次就AC了, 但是速度很不好: 8ms (14%); 主要一个就是在当前root超界, 需要被删除的情况下, 怎样产生新的root的逻辑; 这个问题虽然归类的是easy, 但是我感觉确实还是考到了我的盲点;

这个是discussion最优解, 比我的简练和好看很多, 不过最后速度其实是差不多的:

class Solution {  
    public TreeNode trimBST(TreeNode root, int L, int R) {  
        if (root == null) return null;  

        if (root.val < L) return trimBST(root.right, L, R);  
        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;  
    }  
}

这个代码的基础是一个很关键的intuition, 首先, 他这个代码也是站在root level recursion的角度去思考; 其次, 如果一个root被trim掉了, 那么就是因为这个root超界了; 然后他这里就开始利用BST Property了: 不能仅仅抽象的去理解"超界"这个概念, 具体是超的哪边? 如果是左边, 那么其实整个left child subtree也不需要考虑了, 因为肯定也超界, 右边也是类似的;

他这个算法因为不捉到了这个insight, 所以最后对于base case的处理更加准确, 而我因为没有捕捉到这个base case, 最后recursive call部分的处理就复杂很多, 还需要自己找root successor; 当然最后好歹还是做出来了, 不过如果按照easy的难度设定, 出题人脑子里的解法应该还是这个算法;

题目很新, 暂时还没有别的解法;

Problem Description

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

Difficulty:Easy
Total Accepted:2.4K
Total Submissions:4K
Contributor: tr808
Companies
bloomberg
Related Topics
tree