```
def recover_tree_recursive(self, node):
if not node:
return
def helper(root, prev, l):
if root.left:
prev = helper(root.left, prev, l)
if prev and prev.val > root.val:
if len(l) == 0:
l.append(prev)
l.append(root)
else:
l[1] = root
prev = root
if root.right:
prev = helper(root.right, prev, l)
return prev
p = list()
helper(node, None, p)
if len(p) != 0:
p[0].val, p[1].val = p[1].val, p[0].val
def recover_tree_iterative(self, root):
prev = None
first = None
second = None
while root:
if root.left:
buf = root.left
while buf.right != root and buf.right:
buf = buf.right
if buf.right:
buf.right = root
root = root.left
else:
if prev and prev.val > root.val:
if not first:
first = prev
second = root
prev = root
buf.right = None
root = root.right
else:
if prev and prev.val > root.val:
if not first:
first = prev
second = root
prev = root
root = root.right
if first:
first.val, second.val = second.val, first.val
```