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

• 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

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
n0 = root # the node to be examined currently
n1 = dummy = TreeNode(0) the current parent of n0
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
else:
# 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
break
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
break
node = node.left
n0.val, n1.val = n1.val, n0.val # Switch the values of n0 and n1
# Recover the tree structure