99. Recover Binary Search Tree (Hard) - TengnanYao/daily_leetcode GitHub Wiki

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution(object):
    def recoverTree(self, root):
        """
        :type root: TreeNode
        :rtype: None Do not return anything, modify root in-place instead.
        """
        self.pre, self.nodes = TreeNode(float("-inf")), []
        def inorder(root):
            if root:
                inorder(root.left)
                if root.val < self.pre.val:
                    self.nodes += [self.pre, root]
                self.pre = root
                inorder(root.right)
        inorder(root)
        self.nodes[0].val, self.nodes[-1].val = self.nodes[-1].val, self.nodes[0].val
        return root