LeetCode 099 Recover Binary Search Tree

# 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.
    #     """
    #     # https://discuss.leetcode.com/topic/9305/detail-explain-about-how-morris-traversal-finds-two-incorrect-pointer/2
    #     pre = first = second = None
    #     while root is not None:
    #         if root.left is not None:
    #             temp = root.left
    #             while temp.right is not None and temp.right != root:
    #                 temp = temp.right
    #             if temp.right is not None:
    #                 if pre is not None and pre.val > root.val:
    #                     if first is None:
    #                         first = pre
    #                     second = root
    #                 pre = root
    #                 temp.right = None
    #                 root = root.right
    #             else:
    #                 temp.right = root
    #                 root = root.left
    #         else:
    #             if pre is not None and pre.val > root.val:
    #                 if first is None:
    #                     first = pre
    #                 second = root
    #             pre = root
    #             root = root.right
    #     # only two elements are swapped
    #     if first is not None and second is not None:
    #         first.val, second.val = second.val, first.val


    # https://discuss.leetcode.com/topic/3988/no-fancy-algorithm-just-simple-and-powerful-in-order-traversal/2
    def __init__(self):
        self.first = self.second = None
        self.pre = TreeNode(-sys.maxint - 1)


    def recoverTree(self, root):
        self.traverse(root)
        self.first.val, self.second.val = self.second.val, self.first.val

    def traverse(self, root):
        if root is None:
            return
        self.traverse(root.left)
        if self.pre.val >= root.val:
            if self.first is None:
                self.first = self.pre
            if self.first is not None:
                self.second = root
        self.pre = root
        self.traverse(root.right)