Java solution, iteration version


  • 7
    F

    I just found everyone using recursion to solve this problem. And it's true that recursive solution is much clean and readable. But I just want to write a iterative version which is much longer. Using three loops, one for finding a new root. Second for removing the invalid nodes from left subtree of new root. The last one for removing the invalids nodes from right subtree of new root. Have fun with this solution. lol

    class Solution {
        public TreeNode trimBST(TreeNode root, int L, int R) {
            if (root == null) {
                return root;
            }
            //Find a valid root which is used to return.
            while (root.val < L || root.val > R) {
                if (root.val < L) {
                    root = root.right;
                }
                if (root.val > R) {
                    root = root.left;
                }
            }
            TreeNode dummy = root;
            // Remove the invalid nodes from left subtree.
            while (dummy != null) {
                while (dummy.left != null && dummy.left.val < L) {
                    dummy.left = dummy.left.right; 
                    // If the left child is smaller than L, then we just keep the right subtree of it. 
                }
                dummy = dummy.left;
            }
            dummy = root;
            // Remove the invalid nodes from right subtree
            while (dummy != null) {
                while (dummy.right != null && dummy.right.val > R) {
                    dummy.right = dummy.right.left;
                    // If the right child is biggrt than R, then we just keep the left subtree of it. 
                }
                dummy = dummy.right;
            }
            return root;
        }
    }
    

  • 0
    A

    hahahahahahahahahahaha


Log in to reply
 

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