6/22/2017 - 9:52 AM

## 99. Recover Binary Search Tree

1. Recover Binary Search Tree
``````# 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.
"""
self.node1 = None
self.node2 = None
self.prev = None
self.DFS(root)
temp = self.node1.val
self.node1.val = self.node2.val
self.node2.val = temp
def DFS(self, curr):
if curr == None:
return
self.DFS(curr.left)
if self.prev != None:
# At the very beginning, self.prev = None.
if self.prev.val > curr.val:
# Anormaly detected.
if self.node1 == None:
# There could be 2 anoramlies, e.g. [1,2,7,4,5,6,3,8,9]
# The `3` and `7` are swapped, so (7,4) and (6,3) are anormalies.
self.node1 = self.prev
self.node2 = curr
self.prev = curr
self.DFS(curr.right)``````

https://leetcode.com/problems/recover-binary-search-tree/#/description

Two elements of a binary search tree (BST) are swapped by mistake.

Recover the tree without changing its structure.

Note: A solution using O(n) space is pretty straight forward. Could you devise a constant space solution?