Learning On the Way

99. Recover Binary Search Tree

def recoverTree(self, root: Optional[TreeNode]) -> None: 
    vals = [] 
     
    def addval(cur): 
        if not cur: 
            return 
        addval(cur.left) 
        vals.append(cur.val) 
        addval(cur.right) 
     
    # The first element is always larger than its next one while the second element is always smaller than its previous one.
    def find_two_swapped(nums): 
        x, y = None, None 
        for i in range(len(nums) - 1): 
            if nums[i + 1] < nums[i]: 
                y = nums[i + 1] 
                if x is None: 
                    x = nums[i] 
                else: 
                    break 
        return x, y 
     
    def fixval(cur): 
        if not cur: 
            return 
        if cur.val == x: 
            cur.val = y 
        elif cur.val == y: 
            cur.val = x 
        fixval(cur.left) 
        fixval(cur.right) 
     
    addval(root) 
    x, y = find_two_swapped(vals) 
    fixval(root)

Merge steps

def recoverTree(self, root: TreeNode): 
    stack = [] 
    x = y = pred = None 
     
    while stack or root: 
        while root: 
            stack.append(root) 
            root = root.left 
        root = stack.pop() 
        if pred and root.val < pred.val: 
            y = root 
            if x is None: 
                x = pred  
            else: 
                break 
        pred = root 
        root = root.right 
    x.val, y.val = y.val, x.val