Java easy iterative O(n) space and time solution


  • 1

    This is just a standard iterative inorder traversal of BST. O(n) space for the worst case instead of O(logn) for a skewed tree where all the nodes go to the stack.

     public class Solution {
            public void recoverTree(TreeNode root) {
                if (root == null) {
                    return;
                }
                TreeNode first, second, prev;
                first = second = prev = null;//initialized to null to check if has been assigned value before
                Stack<TreeNode> stack = new Stack<>();
                pushLeft(stack, root);
                while (!stack.isEmpty()) {
                    root = stack.pop();//root is current node
                    pushLeft(stack, root.right);
                    if (prev != null && prev.val > root.val) {
                        if (first == null) {
                            first = prev;//first gets updated for the first time only
                        }
                        second = root;// second gets updated every time prev>root
                    }
                    prev = root;
                }
                int tmp = first.val;
                first.val = second.val;
                second.val = tmp;
            }
            
            private void pushLeft(Stack<TreeNode> stack, TreeNode root) {
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
            }
        }

Log in to reply
 

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