Python | LeetCode

Коммутатор ЦОД MES5500-32 Eltex за 1 минуту - 32x40G/100G (QSFP+ / QSFP28) - 2x10G (SFP+) - RS-232 (RJ-45) - OOB - USB 2.0 Пропускная способность - 6,4 Тбит/с 2 модуля питания с горячей заменой: PM600-220/12 — 220В AC PM600-48/12 — 48В DC Настройка: - CLI через Telnet, SSH (Cisco-like) - веб-интерфейс - SNMP Комплектация: - Сертификат - Паспорт устройства - Комплект крепления в 19"стойку - Пылезащитные заглушки для портов Узнать цену #реклама eltexcm.ru О рекламодателе

#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 Задача: 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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Как повысить эффективность вебинаров? Организация продающего вебинара - не простая задача, ведь необходимо предусмотреть множество деталей: удобную дату, вовлекающий контент, методы продвижения и взаимодействия с участниками. Вебинары от МТС Линк помогают привлекать новых клиентов и увеличивать конверсию из участника в лид. В сервисе доступен анализ поведения пользователей во время вебинара, синхронный перевод, автовебинары и интерактивные инструменты для вовлечения участников. Делимся методичкой с кейсами, чек-листами и инструкциями для маркетологов, PR и event-менеджеров, чтобы сделать вебинары эффективным инструментом для лидогенерации. Получите методичку бесплатно на сайте. Скачать #реклама 16+ mts-link.ru О рекламодателе

#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

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

#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)
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Digital menu board для кафе и ресторанов. От 150.000 р Внедрение цифровых меню бордов "под ключ" от ведущего интегратора Дарим скидку 15% на дизайн для меню бордов. Получите полный расчет, ответив всего на 5 вопросов Перейти на сайт #реклама quiz.in-gr.ru О рекламодателе

#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
        )

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Получите диплом от НИТУ МИСИС в веб-разработке Яндекс Практикум и НИТУ МИСИС приглашают на онлайн-программу «Веб-разработчик» Полноценная учёба в онлайн-формате Зачёты, сессии, лекции и семинары с гибким графиком. На платформе Практикума Гибкая теория, автоматическая проверка заданий и встроенная YandexGPT. Преподаватели НИТУ МИСИС и наставники Яндекс Практикума Они будут проводить занятия и учить вас применять теорию на практике. Студенческий, льготы и диплом гособразца У вас будут все преимущества студента-очника. Доступ к инфраструктуре вуза — кампусам, библиотекам и мероприятиям. Оплатить учёбу можно разными способами: всю сумму сразу, по семестрам или с помощью госкредита — тогда ежемесячный платёж составит от 500 ₽, а государство погасит часть кредита за вас. Подать заявку #реклама 16+ practicum.yandex.ru О рекламодателе

#medium Задача: 99. Recover Binary Search Tree Вам дан корень бинарного дерева поиска (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)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Я айтишник и я устал! Рутина, прокрастинация, куча задач и 0 желания их выполнять. Еще и в семье конфликты. Че делать? Хватит грызть самого себя и заставлять через силу - сделаешь только хуже! Лучше подпишись на того, кто уже не первый год работает с IT-специалистами и помогает им справиться с апатией и прокрастинацией - Психолог с научным подходом. ✔️ Как оторваться от ленты соцсетей и сесть за работу с удовольствием? ✔️ Как перестать работать по выходным и при этом все успевать? ✔️ Как избавиться от постоянной тревожности? ✔️ Как успокоить конфликты в семье и перестать срываться на всех, а вместо этого получить поддержку и понимание со стороны близких? Подписывайся на канал @remizov_changes - начни работать и жить в кайф, не скатываясь в кризисы и выгорание! А в закрепе тебя уже ждут бонусы: 👨🏻‍💻 Видео, в котором ты найдёшь ответ на вопрос «Почему у тебя нет энергии и что с этим делать» + гайд как it-специалисту вернуть энергию, даже если не получается отдохнуть.

Виртуальный сервер в аренду в Турции или России. Отказоустойчивый виртуальный облачный сервер на базе виртуализации VMWARE по модели подписки. - Бесплатная миграция инфраструктуры в Турцию - Размещайте ресурсы в Турции или России и оплачивайте в рублях, турицких лирах или евро. - Храните резервные копии данных за рубежом для минимизации рисков - Продолжайте использовать импортное ПО, скачивайте обновления и патчи, общайтесь с техподдержкой - Доступность сервиса — от 99,982% SLA - Дата центры Tier III в России и Турции - Почасовой биллинг и постоплата Подключите услугу сегодня со скидкой 50% на инфраструктуру. Подать заявку #реклама cloud4y.ru О рекламодателе

#medium Задача: 98. Validate Binary Search Tree Дан корень бинарного дерева. Определите, является ли это дерево допустимым бинарным деревом поиска (BST). Допустимое BST определяется следующим образом: Левое поддерево узла содержит только узлы с ключами, меньшими, чем ключ узла. Правое поддерево узла содержит только узлы с ключами, большими, чем ключ узла. Оба поддерева — левое и правое — также должны быть бинарными деревьями поиска. Пример:

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

👨‍💻 Алгоритм: 1️⃣Давайте воспользуемся порядком узлов при симметричном обходе (inorder traversal): Левый -> Узел -> Правый. Постордер: Здесь узлы перечисляются в порядке их посещения, и вы можете следовать последовательности 1-2-3-4-5 для сравнения различных стратегий. Порядок "Левый -> Узел -> Правый" при симметричном обходе означает, что для BST каждый элемент должен быть меньше следующего. 2️⃣Следовательно, алгоритм с временной сложностью O(N) и пространственной сложностью O(N) может быть простым: Вычислить список симметричного обхода inorder. Проверить, меньше ли каждый элемент в списке inorder следующего за ним. Постордер: 3️⃣Нужно ли сохранять весь список симметричного обхода? На самом деле, нет. Достаточно последнего добавленного элемента inorder, чтобы на каждом шаге убедиться, что дерево является BST (или нет). Следовательно, можно объединить оба шага в один и уменьшить используемое пространство. 😎 Решение:

class Solution:
    def isValidBST(self, root: TreeNode) -> bool:

        def inorder(root):
            if not root:
                return True
            if not inorder(root.left):
                return False
            if root.val <= self.prev:
                return False
            self.prev = root.val
            return inorder(root.right)

        self.prev = -math.inf
        return inorder(root)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Сила предпринимателя — в его окружении Вступай в сообщество предпринимателей Reforma и получи ресурсы и опыт 300+ дейтсвующих предпринимателей из разных ниш, готовых открыто помогать. Без продюсеров, коучей и самозанятых. Большинство из них уже проживали опыт, с которым вы сталкиваетесь каждый день, и будут рады поделиться связями и ресурсами. А на регулярных мероприятиях клуба вы сможете встретиться и пообщаться с основателями топ-компаний — ВкусВилл, PravoTech, OilEnergy, Simple Group и других. Узнаете, как построен бизнес у других и что можно сделать иначе, чтобы быстрее достигать целей. Записывайтесь на экскурсию, и узнайте как сообщество поможет в решении ваших задач! Узнать больше #реклама 16+ reforma.business О рекламодателе

#medium Задача: 97. Interleaving String Даны строки s1, s2 и s3. Необходимо определить, может ли строка s3 быть сформирована путем чередования строк s1 и s2. Чередование двух строк s и t — это конфигурация, при которой s и t делятся на n и m подстрок соответственно так, что: s = s1 + s2 + ... + sn t = t1 + t2 + ... + tm |n - m| ≤ 1 Чередование может быть таким: s1 + t1 + s2 + t2 + s3 + t3 + ... или t1 + s1 + t2 + s2 + t3 + s3 + ... Примечание: a + b означает конкатенацию строк a и b. Пример:

Input: s1 = "aabcc", s2 = "dbbca", s3 = "aadbbcbcac"
Output: true
Explanation: One way to obtain s3 is:
Split s1 into s1 = "aa" + "bc" + "c", and s2 into s2 = "dbbc" + "a".
Interleaving the two splits, we get "aa" + "dbbc" + "bc" + "a" + "c" = "aadbbcbcac".

👨‍💻 Алгоритм: 1️⃣В рекурсивном подходе, описанном выше, рассматривается каждая возможная строка, образованная путем чередования двух заданных строк. Однако возникают случаи, когда та же часть s1 и s2 уже была обработана, но в разных порядках (перестановках). Независимо от порядка обработки, если результирующая строка до этого момента совпадает с требуемой строкой (s3), окончательный результат зависит только от оставшихся частей s1 и s2, а не от уже обработанной части. Таким образом, рекурсивный подход приводит к избыточным вычислениям. 2️⃣Эту избыточность можно устранить, используя мемоизацию вместе с рекурсией. Для этого мы поддерживаем три указателя i, j, k, которые соответствуют индексу текущего символа s1, s2, s3 соответственно. Также мы поддерживаем двумерный массив memo для отслеживания обработанных до сих пор подстрок. memo[i][j] хранит 1/0 или -1 в зависимости от того, была ли текущая часть строк, то есть до i-го индекса для s1 и до j-го индекса для s2, уже оценена. Мы начинаем с выбора текущего символа s1 (на который указывает i). Если он совпадает с текущим символом s3 (на который указывает k), мы включаем его в обработанную строку и вызываем ту же функцию рекурсивно как: is_Interleave(s1, i+1, s2, j, s3, k+1, memo). 3️⃣Таким образом, мы вызвали функцию, увеличив указатели i и k, поскольку часть строк до этих индексов уже была обработана. Аналогично, мы выбираем один символ из второй строки и продолжаем. Рекурсивная функция заканчивается, когда одна из двух строк s1 или s2 полностью обработана. Если, скажем, строка s1 полностью обработана, мы напрямую сравниваем оставшуюся часть s2 с оставшейся частью s3. Когда происходит возврат из рекурсивных вызовов, мы сохраняем значение, возвращенное рекурсивными функциями, в массиве мемоизации memo соответственно, так что когда оно встречается в следующий раз, рекурсивная функция не будет вызвана, но сам массив мемоизации вернет предыдущий сгенерированный результат. 😎 Решение:

class Solution:
    def isInterleave(self, s1: str, s2: str, s3: str) -> bool:
        if len(s3) != len(s1) + len(s2):
            return False
        dp = [[False] * (len(s2) + 1) for _ in range(len(s1) + 1)]
        for i in range(len(s1) + 1):
            for j in range(len(s2) + 1):
                if i == 0 and j == 0:
                    dp[i][j] = True
                elif i == 0:
                    dp[i][j] = dp[i][j - 1] and s2[j - 1] == s3[i + j - 1]
                elif j == 0:
                    dp[i][j] = dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
                else:
                    dp[i][j] = (
                        dp[i - 1][j] and s1[i - 1] == s3[i + j - 1]
                    ) or (dp[i][j - 1] and s2[j - 1] == s3[i + j - 1])
        return dp[len(s1)][len(s2)]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

IT аутсорсинг в СПб! Обслуживание серверов и оргтехники! АйТи аутсорсинг в СПб! Сертифицированные специалисты! Опытная команда IT специалистов! Сертификаты Microsoft! CISCO Mikrotik! 12 лет на рынке! Перейти на сайт #реклама svcnet.ru О рекламодателе

#medium Задача: 96. Unique Binary Search Trees Дано целое число n. Верните количество структурно уникальных деревьев бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Пример:

Input: n = 3
Output: 5

👨‍💻 Алгоритм: 1️⃣Задача состоит в том, чтобы рассчитать количество уникальных BST (бинарных деревьев поиска). Для этого мы можем определить две функции: G(n): количество уникальных BST для последовательности длины n. F(i, n): количество уникальных BST, где число i является корнем BST (1 ≤ i ≤ n). Как видно, G(n) - это именно та функция, которая нам нужна для решения задачи. 2️⃣Позднее мы увидим, что G(n) можно вывести из F(i, n), которая, в свою очередь, рекурсивно относится к G(n). Следуя идее из раздела "Интуиция", мы видим, что общее количество уникальных BST G(n) равно сумме BST F(i, n) с перечислением каждого числа i (1 ≤ i ≤ n) в качестве корня. Таким образом, G(n) = ∑ F(i, n) для i от 1 до n. В частности, для базовых случаев есть только одна комбинация для построения BST из последовательности длиной 1 (только корень) или ничего (пустое дерево). То есть G(0) = 1, G(1) = 1. 3️⃣Дана последовательность от 1 до n, мы выбираем число i из последовательности в качестве корня, тогда количество уникальных BST с указанным корнем, определенным как F(i, n), является декартовым произведением количества BST для его левого и правого поддеревьев, как показано ниже: Например, F(3,7) - количество уникальных деревьев BST с числом 3 в качестве корня. Для построения уникального BST из всей последовательности [1, 2, 3, 4, 5, 6, 7] с 3 в качестве корня, мы должны построить поддерево из его левой подпоследовательности [1, 2] и другое поддерево из правой подпоследовательности [4, 5, 6, 7], а затем соединить их вместе (то есть декартово произведение). Теперь хитрость заключается в том, что мы можем рассматривать количество уникальных BST из последовательности [1,2] как G(2), и количество уникальных BST из последовательности [4, 5, 6, 7] как G(4). Для G(n) не имеет значения содержание последовательности, а только длина последовательности. Следовательно, F(3,7) = G(2)⋅G(4). Обобщая пример, мы можем вывести следующую формулу: F(i, n) = G(i−1)⋅G(n−i) Объединяя формулы (1), (2), мы получаем рекурсивную формулу для G(n), то есть G(n) = ∑ G(i−1)⋅G(n−i) для i от 1 до n. Чтобы вычислить результат функции, мы начинаем с меньшего числа, так как значение G(n) зависит от значений G(0)...G(n−1). 😎 Решение:

class Solution:
    def numTrees(self, n: int) -> int:
        G = [0] * (n + 1)
        G[0], G[1] = 1, 1

        for i in range(2, n + 1):
            for j in range(1, i + 1):
                G[i] += G[j - 1] * G[i - j]

        return G[n]

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Реклама для бизнеса любого уровня в Яндекс Директе Создайте эффективную рекламную кампанию с алгоритмами Яндекс Директа 👌 Начните прямо сейчас ⚡ Зарегистрироваться #реклама direct.yandex.ru О рекламодателе

#medium Задача: 95. Unique Binary Search Trees II Дано целое число n. Верните все структурно уникальные деревья бинарного поиска (BST), которые содержат ровно n узлов с уникальными значениями от 1 до n. Ответ может быть представлен в любом порядке. Пример:

Input: n = 3
Output: [[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]

👨‍💻 Алгоритм: 1️⃣Создайте хеш-карту memo, где memo[(start, end)] содержит список корневых узлов всех возможных BST (деревьев бинарного поиска) с диапазоном значений узлов от start до end. Реализуем рекурсивную функцию allPossibleBST, которая принимает начальный диапазон значений узлов start, конечный диапазон end и memo в качестве параметров. Она возвращает список TreeNode, соответствующих всем BST, которые могут быть сформированы с этим диапазоном значений узлов. Вызываем allPossibleBST(1, n, memo) и выполняем следующее: 2️⃣Объявляем список TreeNode под названием res для хранения списка корневых узлов всех возможных BST. Если start > end, мы добавляем null в res и возвращаем его. Если мы уже решили эту подзадачу, т.е. memo содержит пару (start, end), мы возвращаем memo[(start, end)]. 3️⃣Выбираем значение корневого узла от i = start до end, увеличивая i на 1 после каждой итерации. Рекурсивно вызываем leftSubtrees = allPossibleBST(start, i - 1, memo) и rightSubTrees = allPossibleBST(i + 1, end, memo). Перебираем все пары между leftSubtrees и rightSubTrees и создаем новый корень со значением i для каждой пары. Добавляем корень новообразованного BST в res. Устанавливаем memo[(start, end)] = res и возвращаем res. 😎 Решение:

class Solution:
    def allPossibleBST(self, start, end, memo):
        res = []
        if start > end:
            res.append(None)
            return res
        if (start, end) in memo:
            return memo[(start, end)]

        for i in range(start, end + 1):
            leftSubTrees = self.allPossibleBST(start, i - 1, memo)
            rightSubTrees = self.allPossibleBST(i + 1, end, memo)
            for left in leftSubTrees:
                for right in rightSubTrees:
                    root = TreeNode(i, left, right)
                    res.append(root)

        memo[(start, end)] = res
        return res

    def generateTrees(self, n: int) -> List[Optional[TreeNode]]:
        memo = {}
        return self.allPossibleBST(1, n, memo)

🔥 ТОП ВОПРОСОВ С СОБЕСОВ 🔒 База собесов | 🔒 База тестовых

Оплачиваемая стажировка и трудоустройство без опыта — ну ничего себе 😳 Все возможно с Добровольным квалификационным экзаменом! Это бесплатный проект Правительства Москвы, где ты можешь показать свои знания по специальности, запомниться потенциальным работодателям и получить оффер в престижные компании Москвы. Тебя ждет всего три шага: 1️⃣ Пройди тест После регистрации на сайте ДКЭ тебе будет доступно 70 профессий по 7 направлениям. Выбирай тест по своей специальности и проверь уровень своих знаний! 2️⃣ Реши кейс Если ты успешно сдал тест, тебя пригласят на следующий этап, где ты с другими участниками в команде будешь решать реальный кейс одного из работодателей. 3️⃣ Стань победителем Окажись в числе лучших по общему количеству баллов за оба этапа и получи шанс попасть на оплачиваемую стажировку с дальнейшим трудоустройством. Готов проявить себя? Регистрируйся и начинай проходить тест — https://dke.moscow Реклама. АНО "РАЗВИТИЕ ЧЕЛОВЕЧЕСКОГО КАПИТАЛА", АНО "РЧК". ИНН 7710364647. erid: LjN8KNVQd