LC99 Recover Binary Search Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
"""
main idea:  for a BST, if we do in order traversal, current node's val >= prev node's val;  since there must be a pair of nodes in wrong  order = > there is a value pre'val is bigger than current val (pre is abnomal node ); and there is a value that smaller than previous node(current node is abnomal)   

Note since two nodes to be swapped doesnt have to be continuous, so we need to find two abnomal nodes by traversing 
use inorder traversal, use pre ptr to cache posible abnomal fst node, so as to cache second abnomal node snd;  after all recursion end, switch fst and snd node's VALUE 
    1. inorder traversal, at cur node, before enter node.right, pre = node (cache by reference)
    2. find abnormal node where pre.val >= node.val , fill fst with pre; fill snd with node 
    3. after inorder recursion,  switch fst node's val  with snd node's val  
   time O(N) space O(N)

"""

    def recoverTree(self, root: TreeNode) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        self.pre,self.fst,self.snd = None,None,None
        def inorder(node):
            if not node:
                return 
            inorder(node.left)
            
            # abnomal node: pre.val > node.val 
            if self.pre and node.val < self.pre.val:
                # there are two abnomal nodes in total, so need to record them both
                if not self.fst:
                    self.fst = self.pre
    #??? why we don't use else: because we also need to cover cases pre and current node are abnomal 
                self.snd = node
            self.pre = node   #prev store the root of subtree in this inorder traversal 
            inorder(node.right)
        
        inorder(root)
        self.fst.val,self.snd.val = self.snd.val, self.fst.val