Задача: 99. Recover Binary Search Tree
Сложность: medium

Вам дан корень бинарного дерева поиска (BST), в котором значения ровно двух узлов дерева были поменяны местами по ошибке. Восстановите дерево, не изменяя его структуру.

Пример:

Input: root = [1,3,null,null,2]
Output: [3,1,null,null,2]
Explanation: 3 cannot be a left child of 1 because 3 > 1. Swapping 1 and 3 makes the BST valid.

👨‍💻 Алгоритм:

1️⃣Создайте симметричный обход дерева. Это должен быть почти отсортированный список, в котором поменяны местами только два элемента.

2️⃣Определите два поменянных местами элемента x и y в почти отсортированном массиве за линейное время.

3️⃣Повторно пройдите по дереву. Измените значение x на y и значение y на x.

😎 Решение:

class Solution:
    def recoverTree(self, root: TreeNode) -> None:
        def inorder(r: TreeNode) -> List[int]:
            return inorder(r.left) + [r.val] + inorder(r.right) if r else []

        def find_two_swapped(nums: List[int]) -> (int, int):
            n = len(nums)
            x = y = (
                None  
            )

            for i in range(n - 1):
                if nums[i + 1] < nums[i]:
                    y = nums[i + 1]
                    if x is None:
                        x = nums[i]
                    else:
                        break
            return x, y

        def recover(r: TreeNode, count: int) -> None:
            if r:
                if r.val == x or r.val == y:
                    r.val = y if r.val == x else x
                    count -= 1
                    if count == 0:
                        return
                recover(r.left, count)
                recover(r.right, count)

        nums = inorder(root)
        x, y = find_two_swapped(nums)
        recover(root, 2)

Ставь 👍 и забирай 📚 Базу знаний