Share my O(n) time O(1) space solution

  • 1

    The idea:

    1. morph the tree into a (reversely) ordered linked list using the .left attribute
      as the link. This is done by always taking the leftmost node out of
      the remaining tree. If the taken out node has a right child, let the
      child take its original position. Every time a node is taken out,
      point its right link to its current parent, so that the tree structure can
      be restored later.
    2. Scan the linked list, which holds the tree nodes
      in order, to identify and switch the out-of-place items.
    3. Restore the tree structure from the linked list. Start from the largest node. Every
      time a node is put back to the tree, find its parent by checking its
      .right attribute, place it as the left child of the parent node. If
      the parent node already has a left child, move that child to be the right child of
      the added node.

    Here is the code in Python:

    class Solution:
        # @param root, a tree node
        # @return a tree node
        def recoverTree(self, root):
            if not root: return None
            # Morph the tree into an ordered linked list with an additional link to the parent
            n0 = root # the node to be examined currently
            n1 = dummy = TreeNode(0) the current parent of n0
            head = None #  the head of the resulting reversely ordered linked list
            while n1: 
                if not n0: 
                    n0 = n1
                    n1 = n0.left
                    n0.left = None
                elif n0.left:
                    tmp = n0.left
                    n0.left = n1
                    n1 = n0
                    n0 = tmp
                    n0.left = head
                    head = n0
                    n0 = head.right
                    head.right = n1
            # Identify and recover the switched items
            n0 = n1 = node = head
            while node.left:
                if node.left.val > node.val: 
                    n0 = node # Assign n0 and n1 to the two sides of the first > sign
                    n1 = node.left
                    node = node.left
                node = node.left
            while node.left:
                if node.left.val > node.val: 
                    n1 = node.left # Assign n1 to the left side of the second > sign, if there is any
                node = node.left
            n0.val, n1.val = n1.val, n0.val # Switch the values of n0 and n1
            # Recover the tree structure
            while head:
                node = head
                head = node.left
                node.left = None
                parent = node.right
                node.right = parent.left
                parent.left = node
           return root

Log in to reply