- 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.
- Scan the linked list, which holds the tree nodes
in order, to identify and switch the out-of-place items.
- 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 else: 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 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 while head: node = head head = node.left node.left = None parent = node.right node.right = parent.left parent.left = node return root