99 Recover Binary Search Tree
题目描述：
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?
题目翻译
一个二叉搜索树中两个元素的位置被交换了，在不改变结构的情况下恢复二叉树搜索树
注意：
- 算法空间复杂度为O(n)
解题方案
标签： Tree
思路：
- 正确构造的二叉搜索树的中序遍历是升序的，如果二叉搜索树两个节点的位置错了，那么遍历结果会出现降序，那么出现降序的地方就是被交换的结点，只需将其交换过来就可恢复至正确的二叉搜索树。
- 此时会有两种情况
- 相邻元素出现降序，即当前元素与其后继(当前元素从第一个元素开始标记)出现形成逆序对,对应当前结点与其右子树最左下结点或其父结点交换了位置。此时有且仅有一个逆序对。比如[1-2-3-4-5]->[1-2-4-3-5]。
- 非相邻元素出现降序，此时会出现两个逆序对，比如[1-2-3-4-5]->[1-4-3-2-5]。
- 考虑以上两种情况，设置两个指针(mistake1,mistake2)记录出现逆序的位置(mistake1指向第一个逆序对中的较大元素,mistake2指向其后继结点——对应相邻元素出现逆序，在以后的遍历中更新为第二个逆序对中较小元素——对应非相邻元素出现逆序)
代码：
# Definition for a binary tree node.
# class TreeNode:
# 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.precursor = None # 为Solution类添加数据成员precursor，用于在中序遍历树的过程中，指向当前节点的前驱节点。
# 为Solution类添加数据成员mistake1和mistake2，指向错误的两个节点
self.mistake1 = None
self.mistake2 = None
self.recursive_left_root_right(root) # 调用中序遍历函数，找到错误的节点
if self.mistake1 is not None: # 有错位结点
self.mistake1.val, self.mistake2.val = self.mistake2.val, self.mistake1.val # 交换2个错误节点的值，使二叉搜索树恢复正常
def recursive_left_root_right(self, root): # 中序遍历二叉搜索树
if root == None: # 二叉树为空
return
self.recursive_left_root_right(root.left) # 递归地中序遍历左子树
if self.precursor != None and self.precursor.val > root.val: # 出现逆序对
if self.mistake1 is None: # 第一次出现逆序对
self.mistake1, self.mistake2 = self.precursor, root
else: # 第二次出现逆序对
self.mistake2 = root
self.precursor = root
self.recursive_left_root_right(root.right) # 递归地中序遍历右子树