Java solution, 6 liner


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

  • 10
    B

    I wrote 72 lines for this question....

    public class Solution 
       {
        public TreeNode TrimBST(TreeNode root, int L, int R) 
        {
            var head = FindHead(root, L, R);
    
            var result = DFS(head, L, R);
    
            return head;
        }
    
        private TreeNode FindHead(TreeNode root, int lower, int upper)
        {
            if (root == null) return null;
    
            if (lower <= root.val && root.val <= upper)
            {
                return root;
            }
            else
            {
                if (root.val < lower)
                {
                    return FindHead(root.right, lower, upper);
                }
                else // root.val > upper
                {
                    return FindHead(root.left, lower, upper);
                }
            }
        }
    
        private TreeNode DFS(TreeNode root, int lower, int upper)
        {
            if (root == null) return null;
            
            var newHead = root;
            
            if (lower > root.val || root.val > upper) 
            {
                newHead = FindHead(root, lower, upper);
            }
            
            if (newHead == null) return null;
            
            if (newHead.left != null)
            {
                if (newHead.left.val < lower)
                {
                    newHead.left = DFS(newHead.left.right, lower, upper);
                }
                else
                {
                    newHead.left = DFS(newHead.left, lower, upper);
                }
            }
    
            if (newHead.right != null)
            {
                if (newHead.right.val > upper)
                {
                    newHead.right = DFS(newHead.right.left, lower, upper);
                }
                else
                {
                    newHead.right = DFS(newHead.right, lower, upper);
                }
            }
    
            return newHead;
        }
    }
    

  • 0
    M

    @bacon I feel you. Happens with me, too! :|


  • 3
    R

    @bacon This is awkward, dude!

    I wrote only 40 lines then got it solved!


  • 0
    S
    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);
            }
            else if (root.val > R) {
                return trimBST(root.left, L, R);
            }
            // maybe here can improve ? 
            root.left = trimBST(root.left, L, root.val);
            root.right = trimBST(root.right, root.val, R);
            return root;
        }
    }
    
    

  • 0

    SHAWN GOD!
    (´ ͡༎ຶ ͜ʖ ͡༎ຶ `)


  • 0
    Y

    Great idea! I write into C++ and Python :)

    C++ solution:

    class Solution {
    public:
        TreeNode* trimBST(TreeNode* root, int L, int R) {
            if(!root) return root;
            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;
          }
    };
    

    Python solution:

    class Solution(object):
        def trimBST(self, root, L, R):
            if not root: return None
            if root.val<L: return self.trimBST(root.right,L,R)
            if root.val>R: return self.trimBST(root.left,L,R)
            root.right=self.trimBST(root.right,L,R)
            root.left=self.trimBST(root.left,L,R)
            return root
    

  • 0

    @YangFan You overlooked three spaces you could remove to make it even harder to read.


  • 0
    Y

    @ManuelP Yes, you're right, I overlooked three spaces. Just corrected. Thanks for pointing it out.


  • 0

    @YangFan Hmm, actually you didn't remove them but instead added three more.


  • 0
    Y

    @ManuelP It seems easier to read :p. Anyway, thank you for pointing out my careless mistake.


  • 1

    @YangFan doesn't just replacing the left/right nodes cause memory leaks?


  • 0
    X

    @shawngao 不加判读不会出现null pointer?


  • 1
    F

    @bacon @realhly88 dude! its my 27 lines awkward version.

    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null) {
                return root;
            }
            if (root.val > R) {
                return trimBST(root.left, L, R);
            }
            if (root.val < L) {
                return trimBST(root.right, L, R);
            }
            TreeNode dummy = root;
            while (dummy != null) {
                while (dummy.left != null && dummy.left.val < L) {
                    dummy.left = dummy.left.right;
                }
                dummy = dummy.left;
            }
            dummy = root;
            while (dummy != null) {
                while (dummy.right != null && dummy.right.val > R) {
                    dummy.right = dummy.right.left;
                }
                dummy = dummy.right;
            }
            return root;
        }
    }
    

  • 0
    B

    @FF_Ti Much better than mine.


  • 1
    F

    @bacon Thanks dude, I just abandon the recursive part and rewrite it into purely awkward iterative version. lol

    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null) {
                return root;
            }
            while (root.val < L || root.val > R) {
                if (root.val < L) {
                    root = root.right;
                }
                if (root.val > R) {
                    root = root.left;
                }
            }
            TreeNode dummy = root;
            while (dummy != null) {
                while (dummy.left != null && dummy.left.val < L) {
                    dummy.left = dummy.left.right;
                }
                dummy = dummy.left;
            }
            dummy = root;
            while (dummy != null) {
                while (dummy.right != null && dummy.right.val > R) {
                    dummy.right = dummy.right.left;
                }
                dummy = dummy.right;
            }
            return root;
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.