99. Recover Binary Search Tree

https://leetcode.com/problems/recover-binary-search-tree/

Python

Divide and Conquer

• Transfer to array by inorder travelsal

• Find the swapped elements

• Travel the tree again, and recover the swapped elements

• Time: O(NlogN)

• Space: O(N)

# 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:
    def recoverTree(self, root: Optional[TreeNode]) -> None:
        """
        Do not return anything, modify root in-place instead.
        """
        nums = self.inorder(root)
        
        x, y = None, None
        for i in range(1, len(nums)):
            if nums[i-1] > nums[i]:
                y = nums[i]
                if x is None:
                    x = nums[i-1]
                else:
                    break
        
        self.recover(root, x, y, 2)
    
    def inorder(self, node):
        if not node:
            return []
        
        return self.inorder(node.left) + [node.val] + self.inorder(node.right)
    
    def recover(self, node, x, y, count):
        if not node or count == 0:
            return
        
        if node.val == x:
            node.val = y
            count -= 1
        elif node.val == y:
            node.val = x
            count -= 1
        
        self.recover(node.left, x, y, count)
        self.recover(node.right, x, y, count)