# 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?