Recover Binary Search Tree

只需要记住一个结论，当BST里面的结点被一次误操作破坏了结构之后，整个BST的顺序最多可能有两处出现错位，也可能只出现一次，如果出现了两次，第一次是大的值有问题，第二次是小的有问题，如果只出现一次，则比较的双方就是出问题的结点，这道题要求不用额外空间，则必须使用morris 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.
        """
        pre, cur = root, None
        count = 0
        node1, node2 = None, None
        preNode = None
        while pre:
            cur = pre.left
            if cur:
                while cur.right and cur.right != pre:
                    cur = cur.right
                if not cur.right:
                    cur.right = pre
                    pre = pre.left
                    continue
                else:
                    cur.right = None

            if preNode and count == 0 and pre.val < preNode.val:
                node1 = preNode
                node2 = pre
                count += 1
            elif count == 1 and pre.val < preNode.val:
                node2 = pre

            preNode = pre
            pre = pre.right

        node1.val, node2.val = node2.val, node1.val