# Python O(1) Space and O(n) Solution

• ``````# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
def recoverTree(self, root):
"""
:type root: TreeNode
:rtype: void Do not return anything, modify root in-place instead.
"""
wrongNodes = []
wrongVals = []
lastVal = -sys.maxint - 1
lastElem = None
node = root
while node:
if node.left:
prev = node.left
while prev.right and prev.right != node:
prev = prev.right
if prev.right:
prev.right = None
if lastVal > node.val:
wrongNodes.append(lastElem)
wrongVals.append(lastElem.val)
wrongNodes.append(node)
wrongVals.append(node.val)
lastVal = node.val
lastElem = node
node = node.right
else:
prev.right = node
node = node.left
else:
if lastVal > node.val:
wrongNodes.append(lastElem)
wrongVals.append(lastElem.val)
wrongNodes.append(node)
wrongVals.append(node.val)
lastVal = node.val
lastElem = node
node = node.right
wrongVals.sort()
n = len(wrongVals)
for i in range(n):
wrongNodes[i].val = wrongVals[i]``````

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