A Concise Java Solution using Morris InOrder. O(n) time. O(1) space


  • 5
    2
    public class Solution {
        public void recoverTree(TreeNode root) {
            TreeNode first = null, second = null;
            TreeNode pre = new TreeNode(Integer.MIN_VALUE);
            while (root != null)
            {
                if (root.left != null)
                {
                    TreeNode p = root.left;
                    while (p.right != null && p.right != root)
                        p = p.right;
                    if (p.right == null)
                    {
                        p.right = root;
                        root = root.left;
                        continue;
                    }
                    else
                        p.right = null;
                }
                if (root.val < pre.val)
                {
                    if (first == null)
                    {
                        first = pre;
                    }
                    second = root;
                }
                pre = root;
                root = root.right;
            }
            int tmp = first.val;
            first.val = second.val;
            second.val = tmp;
        }
    }

  • 0
    J

    using morris would change the structure of the tree


Log in to reply
 

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