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?

Solution: 容易犯错的地方就是，如果直接使用两个node1, node2变量，这样非常不好判断条件，如果使用一个prev变量，加上两个node变量就非常容易操作.

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: void Do not return anything, modify root in-place instead.
        """
        self.first= None
        self.two = None
        self.prev = TreeNode(-sys.maxint)
        self.traverse(root)
        temp = self.first.val
        self.first.val = self.two.val
        self.two.val = temp

    def traverse(self, root):
        if root == None:
            return
        self.traverse(root.left)
        if self.first == None and root.val < self.prev.val:
            self.first = self.prev
        if self.first and root.val < self.prev.val:
            self.two = root
        self.prev = root
        self.traverse(root.right)