恢复二叉搜索树

微信图片_20191219215206.jpg

class Solution:
    def __init__(self):
        self.firstNode = None
        self.secondNode = None
        self.preNode = TreeNode(float('-inf'))
    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """

        def order(root):
            if not root:
                return
            order(root.left)
            if self.firstNode == None and self.preNode.val >= root.val:
                self.firstNode = self.preNode
            if self.firstNode and self.preNode.val >= root.val:
                self.secondNode = root
            self.preNode = root
            order(root.right)
        order(root)
        
        if self.firstNode and self.secondNode:
            self.firstNode.val, self.secondNode.val = self.secondNode.val, self.firstNode.val