Java Solution: Morris Traversal and Iteration


  • 1
    A

    For me, the true O(1) space solution means Morris Traversal and an iterative instead of recursive solution.

    public void recoverTree(TreeNode root) {
        List<TreeNode> targets = new ArrayList<TreeNode>(2);
        TreeNode curr = root, prev = null;
        while (curr != null) {
            if (curr.left == null) {
                getTargets(prev, curr, targets);
                prev = curr;
                curr = curr.right;
            } else {
                TreeNode rightmost = curr.left;
                while (rightmost.right != null && rightmost.right != curr)
                    rightmost = rightmost.right;
                if (rightmost.right != curr) {
                    rightmost.right = curr;
                    curr = curr.left;
                } else {
                    rightmost.right = null; // remove the bridge
                    getTargets(prev, curr, targets);
                    prev = curr;
                    curr = curr.right;
                }
            }
        }
        if (targets.size() == 2) {
            int temp = targets.get(0).val;
            targets.get(0).val = targets.get(1).val;
            targets.get(1).val = temp;
        }
    }
    
    private void getTargets(TreeNode prev, TreeNode curr, List<TreeNode> targets) {
        if (prev != null && prev.val > curr.val) {
            if (targets.isEmpty()) {
                targets.add(prev);
                targets.add(curr);
            } else
                targets.set(1, curr);
        }
    }

Log in to reply
 

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