99. Recover Binary Search Tree

99_recover_binary_search_tree.py

class Solution:

    def __init__(self):
        self.swap_a = None
        self.swap_b = None
        self.parent = TreeNode(float('-inf'))

    def inorder(self, n: TreeNode) -> None:
        if n == None:
            return

        self.inorder(n.left)

        if self.swap_a == None and self.parent.val >= n.val:
            self.swap_a = self.parent

        if self.swap_a != None and self.parent.val >= n.val:
            self.swap_b = n

        self.parent = n

        self.inorder(n.right)

    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.inorder(root)
        self.swap_a.val, self.swap_b.val = self.swap_b.val, self.swap_a.val