99. Recover Binary Search Tree

三个指针分别指向前一个节点，和需要交换的两个节点，当出现当前节点比之前节点小的情况时，如果a为空，则把pre赋值给a，如果a不为空，把当前节点赋值给b。

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.pre, self.a, self.b = None, None, None
        self.dfs(root)
        temp = self.a.val
        self.a.val = self.b.val
        self.b.val = temp
        return 
    def dfs(self, root):
        if not root:
            return
        self.dfs(root.left)
        if self.pre and self.pre.val > root.val:
            if not self.a :
                self.a = self.pre
            if self.a:
                self.b = root
        self.pre = root
        self.dfs(root.right)

刚开始忘记更新pre，所以总出错

class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        a = b = pre = None
        stack = []
        node = root
        while stack or node:
            while node:
                stack.append(node)
                node = node.left
            if stack:
                node = stack.pop()
                if pre and pre.val > node.val:
                    if not a and not b:
                        a = pre
                        b = node
                    else:
                        b = node
                        break
                pre = node
                node = node.right
        if a and b:
            a.val, b.val = b.val, a.val