99. Recover Binary Search Tree
这道题因为需要inplace来做， 所以很明显的又是针对recursion traversal的一种变形
# 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.
"""
# 很显然要用inorder
self.prev = None
self.first = None
self.second = None
self.inorder(root)
self.first.val, self.second.val = self.second.val, self.first.val
def inorder(self, root):
if not root:
return
self.inorder(root.left)
if not self.prev or root.val > self.prev.val:
self.prev = root
elif not self.first:
self.first = self.prev
self.second = root
else:
self.second = root
self.inorder(root.right)
