#easy
Задача: 100. Same Tree

Даны корни двух бинарных деревьев p и q. Напишите функцию, чтобы проверить, одинаковы ли они.

Два бинарных дерева считаются одинаковыми, если они структурно идентичны, и узлы имеют одинаковые значения.

Пример:

Input: p = [1,2,3], q = [1,2,3]
Output: true

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

Самая простая стратегия здесь — использовать рекурсию. Проверьте, не равны ли узлы p и q значению None, и равны ли их значения. Если все проверки пройдены успешно, проделайте то же самое для дочерних узлов рекурсивно.

😎 Решение:

class Solution:
    def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
        if not p and not q:
            return True
        if not q or not p:
            return False
        if p.val != q.val:
            return False
        return self.isSameTree(p.right, q.right) and self.isSameTree(
            p.left, q.left
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 101. Symmetric Tree

Дан корень бинарного дерева. Проверьте, является ли это дерево зеркальным отражением самого себя (то есть симметричным относительно своего центра).

Пример:

Input: root = [1,2,2,3,4,4,3]
Output: true

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

1️⃣Дерево симметрично, если левое поддерево является зеркальным отражением правого поддерева.

2️⃣Следовательно, вопрос заключается в том, когда два дерева являются зеркальным отражением друг друга?

Два дерева являются зеркальным отражением друг друга, если:

- Их корни имеют одинаковое значение.
- Правое поддерево каждого дерева является зеркальным отражением левого поддерева другого дерева.

3️⃣Это похоже на человека, смотрящего в зеркало. Отражение в зеркале имеет ту же голову, но правая рука отражения соответствует левой руке настоящего человека и наоборот.

Вышеописанное объяснение естественным образом превращается в рекурсивную функцию.

😎 Решение:

class Solution:
    def isSymmetric(self, root):
        return self.isMirror(root, root)

    def isMirror(self, t1, t2):
        if t1 is None and t2 is None:
            return True
        if t1 is None or t2 is None:
            return False
        return (
            (t1.val == t2.val)
            and self.isMirror(t1.right, t2.left)
            and self.isMirror(t1.left, t2.right)
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 102. Binary Tree Level Order Traversal

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[9,20],[15,7]]

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

1️⃣Самый простой способ решения задачи — использование рекурсии. Сначала убедимся, что дерево не пустое, а затем рекурсивно вызовем функцию helper(node, level), которая принимает текущий узел и его уровень в качестве аргументов.

2️⃣Эта функция выполняет следующее:

Выходной список здесь называется levels, и, таким образом, текущий уровень — это просто длина этого списка len(levels). Сравниваем номер текущего уровня len(levels) с уровнем узла level. Если вы все еще на предыдущем уровне, добавьте новый, добавив новый список в levels.

3️⃣Добавьте значение узла в последний список в levels.

Рекурсивно обработайте дочерние узлы, если они не равны None: helper(node.left / node.right, level + 1).

😎 Решение:

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        levels = []
        if not root:
            return levels

        def helper(node: TreeNode, level: int) -> None:
            if len(levels) == level:
                levels.append([])

            levels[level].append(node.val)

            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 103. Binary Tree Zigzag Level Order Traversal

Дан корень бинарного дерева. Верните обход узлов дерева по уровням в виде зигзага (то есть слева направо, затем справа налево для следующего уровня и чередуйте далее).

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[3],[20,9],[15,7]]

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

1️⃣Мы также можем реализовать поиск в ширину (BFS) с использованием одного цикла. Трюк заключается в том, что мы добавляем узлы для посещения в очередь, а узлы разных уровней разделяем с помощью какого-то разделителя (например, пустого узла). Разделитель отмечает конец уровня, а также начало нового уровня.

2️⃣Здесь мы принимаем второй подход, описанный выше. Можно начать с обычного алгоритма BFS, к которому мы добавляем элемент порядка зигзага с помощью deque (двусторонней очереди).

3️⃣Для каждого уровня мы начинаем с пустого контейнера deque, который будет содержать все значения данного уровня. В зависимости от порядка каждого уровня, т.е. либо слева направо, либо справа налево, мы решаем, с какого конца deque добавлять новый элемент.

😎 Решение:

from collections import deque

class Solution:
    def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
        ret = []
        level_list = deque()
        if root is None:
            return []
        node_queue = deque([root, None])
        is_order_left = True

        while len(node_queue) > 0:
            curr_node = node_queue.popleft()

            if curr_node:
                if is_order_left:
                    level_list.append(curr_node.val)
                else:
                    level_list.appendleft(curr_node.val)

                if curr_node.left:
                    node_queue.append(curr_node.left)
                if curr_node.right:
                    node_queue.append(curr_node.right)
            else:
                ret.append(level_list)
                if len(node_queue) > 0:
                    node_queue.append(None)

                level_list = deque()
                is_order_left = not is_order_left

        return ret

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 104. Maximum Depth of Binary Tree

Дан корень бинарного дерева, верните его максимальную глубину.

Максимальная глубина бинарного дерева — это количество узлов вдоль самого длинного пути от корневого узла до самого удалённого листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 3

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

1️⃣Можно обойти дерево, используя стратегию поиска в глубину (DFS) или поиска в ширину (BFS).

2️⃣Для данной задачи подойдет несколько способов.

3️⃣Здесь мы демонстрируем решение, реализованное с использованием стратегии DFS и рекурсии.

😎 Решение:

class Solution:
    def maxDepth(self, root: TreeNode) -> int:
        if root is None:
            return 0
        else:
            left_height = self.maxDepth(root.left)
            right_height = self.maxDepth(root.right)
            return max(left_height, right_height) + 1

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 105. Construct Binary Tree from Preorder and Inorder Traversal

Даны два массива целых чисел: preorder и inorder, где preorder — это результат преордер обхода бинарного дерева, а inorder — результат инордер обхода того же дерева. Постройте и верните бинарное дерево.

Пример:

Input: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
Output: [3,9,20,null,null,15,7]

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

1️⃣Создайте хеш-таблицу для записи соотношения значений и их индексов в массиве inorder, чтобы можно было быстро найти позицию корня.

2️⃣Инициализируйте переменную целочисленного типа preorderIndex для отслеживания элемента, который будет использоваться для создания корня. Реализуйте рекурсивную функцию arrayToTree, которая принимает диапазон массива inorder и возвращает построенное бинарное дерево:
Если диапазон пуст, возвращается null;
Инициализируйте корень элементом preorder[preorderIndex], затем увеличьте preorderIndex;
Рекурсивно используйте левую и правую части массива inorder для построения левого и правого поддеревьев.

3️⃣Просто вызовите функцию рекурсии с полным диапазоном массива inorder.

😎 Решение:

class Solution:
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:

        def array_to_tree(left, right):
            nonlocal preorder_index
            if left > right:
                return None

            root_value = preorder[preorder_index]
            root = TreeNode(root_value)

            preorder_index += 1

            root.left = array_to_tree(left, inorder_index_map[root_value] - 1)
            root.right = array_to_tree(inorder_index_map[root_value] + 1, right)

            return root

        preorder_index = 0
        inorder_index_map = {}
        for index, value in enumerate(inorder):
            inorder_index_map[value] = index

        return array_to_tree(0, len(preorder) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 106. Construct Binary Tree from Inorder and Postorder Traversal

Даны два массива целых чисел: inorder и postorder, где inorder — это массив обхода в глубину бинарного дерева слева направо, а postorder — это массив обхода в глубину после обработки всех потомков узла. Постройте и верните соответствующее бинарное дерево.

Пример:

Input: inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
Output: [3,9,20,null,null,15,7]

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

1️⃣Создайте хэш-таблицу (hashmap) для хранения соответствия значений и их индексов в массиве обхода inorder.

2️⃣Определите вспомогательную функцию helper, которая принимает границы левой и правой части текущего поддерева в массиве inorder. Эти границы используются для проверки, пусто ли поддерево. Если левая граница больше правой (in_left > in_right), то поддерево пустое и функция возвращает None.

3️⃣Выберите последний элемент в массиве обхода postorder в качестве корня. Значение корня имеет индекс index в обходе inorder. Элементы от in_left до index - 1 принадлежат левому поддереву, а элементы от index + 1 до in_right — правому поддереву. Согласно логике обхода postorder, сначала рекурсивно строится правое поддерево helper(index + 1, in_right), а затем левое поддерево helper(in_left, index - 1). Возвращается корень.

😎 Решение:

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        def helper(in_left: int, in_right: int) -> TreeNode:
            if in_left > in_right:
                return None

            val = postorder.pop()
            root = TreeNode(val)

            index = idx_map[val]

            root.right = helper(index + 1, in_right)
            root.left = helper(in_left, index - 1)
            return root

        idx_map = {val: idx for idx, val in enumerate(inorder)}
        return helper(0, len(inorder) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

10$ за техническое собеседование на английском языке:

1. Отправьте запись технического собеседования на английском языке файлом на этот аккаунт
2. Добавьте ссылку на вакансию или пришлите название компании и должность
3. Напишите номер кошелка USDT (Tether) на который отправить 10$

🛡 Важно:

– Запись будет использована только для сбора данных о вопросах
– Вы останетесь анонимны
– Запись нигде не будет опубликована

🤝 Условия:

– Внятный звук, различимая речь
– Допустимые профессии:
• Любые программисты
• DevOps
• Тестировщики
• Дата сайнтисты
• Бизнес/Системные аналитики
• Прожекты/Продукты
• UX/UI и продукт дизайнеры

#medium
Задача: 107. Binary Tree Level Order Traversal II

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

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: [[15,7],[9,20],[3]]

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

1️⃣Инициализируйте список вывода levels. Длина этого списка определяет, какой уровень в данный момент обновляется. Вам следует сравнить этот уровень len(levels) с уровнем узла level, чтобы убедиться, что вы добавляете узел на правильный уровень. Если вы все еще находитесь на предыдущем уровне, добавьте новый уровень, вставив новый список в levels.

2️⃣Добавьте значение узла в последний уровень в levels.

3️⃣Рекурсивно обработайте дочерние узлы, если они не равны None, используя функцию helper(node.left / node.right, level + 1).

😎 Решение:

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        levels = []
        if not root:
            return levels

        def helper(node: Optional[TreeNode], level: int) -> None:
            if len(levels) == level:
                levels.append([])

            levels[level].append(node.val)

            if node.left:
                helper(node.left, level + 1)
            if node.right:
                helper(node.right, level + 1)

        helper(root, 0)
        return levels[::-1]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 108. Convert Sorted Array to Binary Search Tree

Дан массив целых чисел nums, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте двоичное дерево поиска.

Пример:

Input: nums = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: [0,-10,5,null,-3,null,9] is also accepted:

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

1️⃣Инициализация функции помощника: Реализуйте функцию помощника helper(left, right), которая строит двоичное дерево поиска (BST) из элементов массива nums между индексами left и right.
Если left > right, это означает, что элементов для построения поддерева нет, возвращаем None.

2️⃣Выбор корня и разделение массива:
Выберите элемент в середине для корня: p = (left + right) // 2.
Инициализируйте корень: root = TreeNode(nums[p]).

3️⃣Рекурсивное построение поддеревьев:
Рекурсивно стройте левое поддерево: root.left = helper(left, p - 1).
Рекурсивно стройте правое поддерево: root.right = helper(p + 1, right).
В качестве результата возвращайте helper(0, len(nums) - 1), начиная с корня дерева.

😎 Решение:

class Solution:
    def sortedArrayToBST(self, nums):
        def helper(left, right):
            if left > right:
                return None

            p = (left + right) // 2
            root = TreeNode(nums[p])
            root.left = helper(left, p - 1)
            root.right = helper(p + 1, right)
            return root

        return helper(0, len(nums) - 1)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 109. Convert Sorted List to Binary Search Tree

Дана голова односвязного списка, элементы которого отсортированы в порядке возрастания. Преобразуйте его в сбалансированное по высоте бинарное дерево поиска.

Пример:

Input: head = [-10,-3,0,5,9]
Output: [0,-3,9,-10,null,5]
Explanation: One possible answer is [0,-3,9,-10,null,5], which represents the shown height balanced BST.

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

1️⃣Поскольку нам дан односвязный список, а не массив, у нас нет прямого доступа к элементам списка по индексам. Нам нужно определить средний элемент односвязного списка. Мы можем использовать подход с двумя указателями для нахождения среднего элемента списка. В основном, у нас есть два указателя: slow_ptr и fast_ptr. slow_ptr перемещается на один узел за раз, тогда как fast_ptr перемещается на два узла за раз. К тому времени, как fast_ptr достигнет конца списка, slow_ptr окажется в середине списка. Для списка с четным количеством элементов любой из двух средних элементов может стать корнем BST.

2️⃣Как только мы находим средний элемент списка, мы отсоединяем часть списка слева от среднего элемента. Мы делаем это, сохраняя prev_ptr, который указывает на узел перед slow_ptr, т.е. prev_ptr.next = slow_ptr. Для отсоединения левой части мы просто делаем prev_ptr.next = None.

3️⃣Для создания сбалансированного по высоте BST нам нужно передать только голову связанного списка в функцию, которая преобразует его в BST. Таким образом, мы рекурсивно работаем с левой половиной списка, передавая оригинальную голову списка, и с правой половиной, передавая slow_ptr.next в качестве головы.

😎 Решение:

class Solution:

    def findMiddle(self, head: ListNode) -> ListNode:
        prevPtr = None
        slowPtr = head
        fastPtr = head
        while fastPtr and fastPtr.next:
            prevPtr = slowPtr
            slowPtr = slowPtr.next
            fastPtr = fastPtr.next.next
        if prevPtr:
            prevPtr.next = None
        return slowPtr

    def sortedListToBST(self, head: ListNode) -> TreeNode:
        if not head:
            return None
        mid = self.findMiddle(head)
        node = TreeNode(mid.val)
        if head == mid:
            return node
        node.left = self.sortedListToBST(head)
        node.right = self.sortedListToBST(mid.next)
        return node

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 110. Balanced Binary Tree

Дано бинарное дерево, определите, является ли оно
сбалансированным по высоте.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: true

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

1️⃣Сначала мы определяем функцию height, которая для любого узла p в дереве T возвращает:
-1, если p является пустым поддеревом, т.е. null;
1 + max(height(p.left), height(p.right)) в противном случае.

2️⃣Теперь, когда у нас есть метод для определения высоты дерева, остается только сравнить высоты детей каждого узла. Дерево T с корнем r является сбалансированным тогда и только тогда, когда высоты его двух детей отличаются не более чем на 1 и поддеревья каждого ребенка также сбалансированы.

3️⃣Следовательно, мы можем сравнить высоты двух дочерних поддеревьев, а затем рекурсивно проверить каждое из них:
Если root == NULL, возвращаем true.
Если abs(height(root.left) - height(root.right)) > 1, возвращаем false.
В противном случае возвращаем isBalanced(root.left) && isBalanced(root.right).

😎 Решение:

class Solution:
    def height(self, root: TreeNode) -> int:
        if not root:
            return -1
        return 1 + max(self.height(root.left), self.height(root.right))

    def isBalanced(self, root: TreeNode) -> bool:
        if not root:
            return True
        return (
            abs(self.height(root.left) - self.height(root.right)) < 2
            and self.isBalanced(root.left)
            and self.isBalanced(root.right)
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 111. Minimum Depth of Binary Tree

Дано бинарное дерево, найдите его минимальную глубину.

Минимальная глубина - это количество узлов вдоль самого короткого пути от корневого узла до ближайшего листового узла.

Пример:

Input: root = [3,9,20,null,null,15,7]
Output: 2

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

1️⃣Мы будем использовать метод обхода в глубину (dfs) с корнем в качестве аргумента.
Базовое условие рекурсии: это для узла NULL, в этом случае мы должны вернуть 0.

2️⃣Если левый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для правого ребенка корневого узла, что равно 1 + dfs(root.right).

3️⃣Если правый ребенок корня является NULL: тогда мы должны вернуть 1 + минимальную глубину для левого ребенка корневого узла, что равно 1 + dfs(root.left). Если оба ребенка не являются NULL, тогда вернуть 1 + min(dfs(root.left), dfs(root.right)).

😎 Решение:

class Solution:
    def minDepth(self, root):
        def dfs(root):
            if root is None:
                return 0
            if root.left is None:
                return 1 + dfs(root.right)
            elif root.right is None:
                return 1 + dfs(root.left)
            return 1 + min(dfs(root.left), dfs(root.right))

        return dfs(root)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#easy
Задача: 112. Path Sum

Дан корень бинарного дерева и целое число targetSum. Верните true, если в дереве существует путь от корня до листа, такой, что сумма всех значений вдоль пути равна targetSum.

Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
Output: true
Explanation: The root-to-leaf path with the target sum is shown.

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

1️⃣Инициализация стека: Начать с помещения в стек корневого узла и соответствующей оставшейся суммы, равной sum - root.val.

2️⃣Обработка узлов: Извлечь текущий узел из стека и вернуть True, если оставшаяся сумма равна 0 и узел является листом.

3️⃣Добавление дочерних узлов в стек: Если оставшаяся сумма не равна нулю или узел не является листом, добавить в стек дочерние узлы с соответствующими оставшимися суммами.

😎 Решение:

class Solution:
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        if not root:
            return False

        de = [
            (root, sum - root.val),
        ]
        while de:
            node, curr_sum = de.pop()
            if not node.left and not node.right and curr_sum == 0:
                return True
            if node.right:
                de.append((node.right, curr_sum - node.right.val))
            if node.left:
                de.append((node.left, curr_sum - node.left.val))
        return False

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#Medium
Задача: 113. Path Sum II

Дан корень бинарного дерева и целое число targetSum. Верните все пути от корня до листа, где сумма значений узлов в пути равна targetSum. Каждый путь должен быть возвращён как список значений узлов, а не ссылок на узлы.

Путь от корня до листа — это путь, начинающийся от корня и заканчивающийся на любом листовом узле. Лист — это узел без детей.

Пример:

Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22

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

1️⃣Определение функции recurseTree: Функция принимает текущий узел (node), оставшуюся сумму (remainingSum), которая необходима для продолжения поиска вниз по дереву, и список узлов (pathNodes), который содержит все узлы, встреченные до текущего момента на данной ветке.

2️⃣Проверка условий: На каждом шаге проверяется, равна ли оставшаяся сумма значению текущего узла. Если это так и текущий узел является листом, текущий путь (pathNodes) добавляется в итоговый список путей, который должен быть возвращен.

3️⃣Обработка всех ветвей: Учитывая, что значения узлов могут быть отрицательными, необходимо исследовать все ветви дерева до самых листьев, независимо от текущей суммы по пути.

😎 Решение:

class TreeNode:
    def __init__(self, x: int) -> None:
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def recurseTree(
        self,
        node: TreeNode,
        remainingSum: int,
        pathNodes: List[int],
        pathsList: List[List[int]],
    ) -> None:

        if not node:
            return

        pathNodes.append(node.val)

        if remainingSum == node.val and not node.left and not node.right:
            pathsList.append(list(pathNodes))
        else:
            self.recurseTree(
                node.left, remainingSum - node.val, pathNodes, pathsList
            )
            self.recurseTree(
                node.right, remainingSum - node.val, pathNodes, pathsList
            )

        pathNodes.pop()

    def pathSum(self, root: TreeNode, sum: int) -> List[List[int]]:
        pathsList = []
        self.recurseTree(root, sum, [], pathsList)
        return pathsList

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#Medium
Задача: 114. Flatten Binary Tree to Linked List

"Связный список" должен использовать тот же класс TreeNode, где указатель на правого ребенка указывает на следующий узел в списке, а указатель на левого ребенка всегда равен null.
"Связный список" должен быть в том же порядке, что и обход бинарного дерева в прямом порядке.

Пример:

Input: root = [1,2,5,3,4,null,6]
Output: [1,null,2,null,3,null,4,null,5,null,6]

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

1️⃣Плоское преобразование дерева: Рекурсивно преобразуем левое и правое поддеревья заданного узла, сохраняя соответствующие конечные узлы в leftTail и rightTail.

2️⃣Установка соединений: Если у текущего узла есть левый ребенок, выполняем следующие соединения:
leftTail.right = node.right
node.right = node.left
node.left = None

3️⃣Возврат конечного узла: Возвращаем rightTail, если у узла есть правый ребенок, иначе возвращаем leftTail.

😎 Решение:

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:

    def flattenTree(self, node: TreeNode) -> TreeNode:
        if not node:
            return None

        if not node.left and not node.right:
            return node

        leftTail = self.flattenTree(node.left)
        rightTail = self.flattenTree(node.right)

        if leftTail:
            leftTail.right = node.right
            node.right = node.left
            node.left = None

        return rightTail if rightTail else leftTail

    def flatten(self, root: TreeNode) -> None:
        self.flattenTree(root)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 115. Distinct Subsequences

"Даны две строки s и t. Верните количество различных подпоследовательностей строки s, которые равны строке t.

Тестовые примеры сгенерированы таким образом, что ответ укладывается в 32-битное целое число со знаком."

Пример:

Input: s = "rabbbit", t = "rabbit"
Output: 3
Explanation:
As shown below, there are 3 ways you can generate "rabbit" from s.
rabbbit
rabbbit
rabbbit

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

1️⃣Определите функцию с названием recurse, которая принимает два целочисленных значения i и j. Первое значение представляет текущий обрабатываемый символ в строке S, а второе - текущий символ в строке T. Инициализируйте словарь под названием memo, который будет кэшировать результаты различных вызовов рекурсии.**

2️⃣Проверьте базовый случай. Если одна из строк закончилась, возвращается 0 или 1 в зависимости от того, удалось ли обработать всю строку T или нет. Есть ещё один базовый случай, который следует рассмотреть. Если оставшаяся длина строки S меньше, чем у строки T, то совпадение невозможно. Если это обнаруживается, то рекурсия также обрезается и возвращается 0.**

3️⃣Затем проверяем, существует ли текущая пара индексов в нашем словаре. Если да, то просто возвращаем сохранённое/кэшированное значение. Если нет, то продолжаем обычную обработку. Сравниваем символы s[i] и t[j]. Сохраняем результат вызова recurse(i + 1, j) в переменную. Как упоминалось ранее, результат этой рекурсии необходим, независимо от совпадения символов. Если символы совпадают, добавляем к переменной результат вызова recurse(i + 1, j + 1). Наконец, сохраняем значение этой переменной в словаре с ключом (i, j) и возвращаем это значение в качестве ответа.

😎 Решение:

class Solution:
    def numDistinct(self, s: str, t: str) -> int:

        memo = {}

        def uniqueSubsequences(i: int, j: int) -> int:

            M, N = len(s), len(t)

            if i == M or j == N or M - i < N - j:
                return int(j == len(t))

            if (i, j) in memo:
                return memo[i, j]

            ans = uniqueSubsequences(i + 1, j)

            if s[i] == t[j]:
                ans += uniqueSubsequences(i + 1, j + 1)

            memo[i, j] = ans
            return ans

        return uniqueSubsequences(0, 0)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 116. Populating Next Right Pointers in Each Node

Вам дано идеальное бинарное дерево, где все листья находятся на одном уровне, и у каждого родителя есть два детей. Бинарное дерево имеет следующее определение:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next так, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1️⃣Инициализируйте очередь Q, которую мы будем использовать во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда речь идет о определении уровня конкретного узла. Можно добавлять в очередь пару (узел, уровень), и каждый раз, когда добавляются дети узла, мы добавляем (node.left, parent_level + 1) и (node.right, parent_level + 1). Этот подход не будет очень эффективен для нашего алгоритма, так как нам нужны все узлы на одном уровне, и для этого потребуется еще одна структура данных.

2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня заключается в использовании некоторой разграничительной метки между уровнями. Обычно мы вставляем в очередь элемент NULL, который отмечает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого количества памяти, пропорционально количеству уровней в дереве.

3️⃣Подход, который мы будем использовать здесь, будет иметь структуру вложенных циклов, чтобы обойти необходимость указателя NULL. По сути, на каждом шаге мы записываем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и не более. К моменту, когда мы закончим обработку заданного количества элементов, в очереди будут все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Поскольку на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

import collections

class Solution:
    def connect(self, root: "Node") -> "Node":
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)
            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 117. Populating Next Right Pointers in Each Node II

Вам дано бинарное дерево:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Заполните каждый указатель next, чтобы он указывал на следующий правый узел. Если следующего правого узла нет, указатель next должен быть установлен в NULL.

Изначально все указатели next установлены в NULL.

Пример:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

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

1️⃣Инициализируйте очередь Q, которая будет использоваться во время обхода. Существует несколько способов реализации обхода в ширину, особенно когда дело доходит до определения уровня конкретного узла. Можно добавить в очередь пару (узел, уровень), и каждый раз, когда мы добавляем детей узла, мы добавляем (node.left, parent_level+1) и (node.right, parent_level+1). Этот подход может оказаться неэффективным для нашего алгоритма, так как нам нужны все узлы на одном уровне, и потребуется дополнительная структура данных.

2️⃣Более эффективный с точки зрения памяти способ разделения узлов одного уровня - использовать разграничение между уровнями. Обычно мы вставляем в очередь элемент NULL, который обозначает конец предыдущего уровня и начало следующего. Это отличный подход, но он все равно потребует некоторого объема памяти, пропорционального количеству уровней в дереве.

3️⃣Подход, который мы будем использовать, предполагает структуру вложенных циклов, чтобы обойти необходимость NULL указателя. По сути, на каждом шаге мы фиксируем размер очереди, который всегда соответствует всем узлам на определенном уровне. Как только мы узнаем этот размер, мы обрабатываем только это количество элементов и больше ничего. К тому времени, как мы закончим обработку заданного количества элементов, в очереди окажутся все узлы следующего уровня. Вот псевдокод для этого:

while (!Q.empty())
{
    size = Q.size()
    for i in range 0..size
    {
        node = Q.pop()
        Q.push(node.left)
        Q.push(node.right)
    }
}

Мы начинаем с добавления корня дерева в очередь. Так как на уровне 0 есть только один узел, нам не нужно устанавливать какие-либо соединения, и мы можем перейти к циклу while.

😎 Решение:

class Solution:
    def connect(self, root: Optional["Node"]) -> Optional["Node"]:
        if not root:
            return root

        Q = collections.deque([root])

        while Q:
            size = len(Q)

            for i in range(size):
                node = Q.popleft()
                if i < size - 1:
                    node.next = Q[0]
                if node.left:
                    Q.append(node.left)
                if node.right:
                    Q.append(node.right)

        return root

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#medium
Задача: 122. Best Time to Buy and Sell Stock II

Вам дан массив целых чисел prices, где prices[i] — это цена данной акции в i-й день.

Каждый день вы можете решить купить и/или продать акцию. Вы можете держать в руках только одну акцию за раз. Однако вы можете купить её и сразу же продать в тот же день.

Найдите и верните максимальную прибыль, которую вы можете получить.

Пример:

Input: prices = [7,1,5,3,6,4]
Output: 7
Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4.
Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Total profit is 4 + 3 = 7.

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

1️⃣Предположим, что дан массив:

\[ 7, 1, 5, 3, 6, 4 \]

Если мы изобразим числа данного массива на графике, мы получим: *приложенное изображение*

2️⃣Анализируя график, мы замечаем, что точки интереса — это последовательные впадины и пики.

Математически говоря:
Общая прибыль = ∑ (высота(пик i) - высота(впадина i))

3️⃣Ключевой момент заключается в том, что мы должны учитывать каждый пик, следующий сразу за впадиной, чтобы максимизировать прибыль. Если мы пропустим один из пиков (пытаясь получить больше прибыли), мы потеряем прибыль по одной из сделок, что приведет к общей меньшей прибыли.

Например, в вышеуказанном случае, если мы пропустим пик i и впадину j, пытаясь получить больше прибыли, рассматривая точки с большей разницей в высотах, чистая прибыль всегда будет меньше, чем та, которая была бы получена при их учете, поскольку C всегда будет меньше, чем A+B.

😎 Решение:

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        i = 0
        valley = prices[0]
        peak = prices[0]
        maxprofit = 0
        while i < len(prices) - 1:
            while i < len(prices) - 1 and prices[i] >= prices[i + 1]:
                i += 1
            valley = prices[i]
            while i < len(prices) - 1 and prices[i] <= prices[i + 1]:
                i += 1
            peak = prices[i]
            maxprofit += peak - valley
        return maxprofit

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых

#hard
Задача: 124. Binary Tree Maximum Path Sum

Вам дан массив цен, где prices[i] — это цена данной акции в i-й день.

Найдите максимальную прибыль, которую вы можете получить. Вы можете совершить не более двух транзакций.

Пример:

Input: prices = [3,3,5,0,0,3,1,4]
Output: 6
Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3.
Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1

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

1️⃣Наивная реализация этой идеи заключалась бы в разделении последовательностей на две части и последующем перечислении каждой из подпоследовательностей, хотя это определенно не самое оптимизированное решение.

Для последовательности длиной N у нас было бы N возможных разделений (включая отсутствие разделения), каждый элемент был бы посещен один раз в каждом разделении. В результате общая временная сложность этой наивной реализации составила бы O(N²).

2️⃣Мы могли бы сделать лучше, чем наивная реализация O(N²). Что касается алгоритмов разделяй и властвуй,
одна из общих техник, которую мы можем применить для оптимизации временной сложности, называется динамическим программированием (DP), где мы меняем менее повторяющиеся вычисления на некоторое дополнительное пространство.

В алгоритмах динамического программирования обычно мы создаем массив одного или двух измерений для сохранения промежуточных оптимальных результатов. В данной задаче мы бы использовали два массива, один массив сохранял бы результаты последовательности слева направо, а другой массив сохранял бы результаты последовательности справа налево. Для удобства мы могли бы назвать это двунаправленным динамическим программированием.

3️⃣Сначала мы обозначаем последовательность цен как Prices[i], с индексом начиная от 0 до N-1. Затем мы определяем два массива, а именно left_profits[i] и right_profits[i].

Как следует из названия, каждый элемент в массиве left_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в левой подпоследовательности цен от индекса ноль до i, (т.е. Prices[0], Prices[1], ... Prices[i]).
Например, для подпоследовательности [7, 1, 5] соответствующий left_profits[2] будет равен 4, что означает покупку по цене 1 и продажу по цене 5.

И каждый элемент в массиве right_profits[i] будет содержать максимальную прибыль, которую можно получить от выполнения одной транзакции в правой подпоследовательности цен от индекса i до N-1, (т.е. Prices[i], Prices[i+1], ... Prices[N-1]).
Например, для правой подпоследовательности [3, 6, 4] соответствующий right_profits[3] будет равен 3, что означает покупку по цене 3 и продажу по цене 6.

Теперь, если мы разделим последовательность цен вокруг элемента с индексом i на две подпоследовательности, с левыми подпоследовательностями как Prices[0], Prices[1], ... Prices[i] и правой подпоследовательностью как Prices[i+1], ... Prices[N-1],
то общая максимальная прибыль, которую мы получим от этого разделения (обозначенная как max_profits[i]), может быть выражена следующим образом:
max_profits[i] = left_profits[i] + right_profits[i+1]

😎 Решение:

class Solution(object):
    def maxProfit(self, prices: List[int]) -> int:
        if len(prices) <= 1:
            return 0

        left_min = prices[0]
        right_max = prices[-1]

        length = len(prices)
        left_profits = [0] * length
        # pad the right DP array with an additional zero for convenience.
        right_profits = [0] * (length + 1)

        # construct the bidirectional DP array
        for l in range(1, length):
            left_profits[l] = max(left_profits[l - 1], prices[l] - left_min)
            left_min = min(left_min, prices[l])

            r = length - 1 - l
            right_profits[r] = max(right_profits[r + 1], right_max - prices[r])
            right_max = max(right_max, prices[r])

        max_profit = 0
        for i in range(0, length):
            max_profit = max(max_profit, left_profits[i] + right_profits[i + 1])

        return max_profit

🔥 ТОП ВОПРОСОВ С СОБЕСОВ

🔒 База собесов | 🔒 База тестовых