Python | LeetCode

Бесплатное IT-образование в 2024 Отобрали для вас полезные телеграм-каналы, которые помогут освоить IT-направления Выбирайте нужное и подписывайтесь: — Frontend: t.me/+qWPopdiaxVMzZDgy — Backend: t.me/+X-zQb-NgzGNhMzRi — GitHub: t.me/+3BVAmDixuO9lYTFi — Книги айти: t.me/+IG2NAVECUXs4MGYy — Python: t.me/+vBSA5zgB_gA0OWRi — Java: t.me/+3BRKfZ09ewg0NDJi — C#: t.me/+O3pnFY4bpF5hNTEy — С/С++: t.me/+PGxPXpZZczQxODcy — Базы Данных & SQL: t.me/+530qWWydM8ExZjk6 — Golang: t.me/+FvTd7F-O-NNmNGMy — PHP: t.me/+jBvbaet0vpplNDQy — Моб. разработка: t.me/+Ikx5H4MrPihlOWZi — Разработка игр: t.me/+Z34knEvL8P9lZTAy — DevOps: t.me/+3wSgqmP5NOBhZGUy — Data Science: t.me/+-CuoNNa6P7VjOTRi — ИБ: t.me/+4jo8N5jtGDs1NTli — Тестирование: t.me/+MvFXlXbmmPFkM2Ey — Маркетинг: t.me/+lgiFPJTYp8M0ZjRi — Дизайн: t.me/+gmflvDFPc_c1YmIy Подписаться #реклама 16+ О рекламодателе

#medium Задача: 339. Nested List Weight Sum Вам дан вложенный список целых чисел nestedList. Каждый элемент либо целое число, либо список, элементы которого также могут быть целыми числами или другими списками. Глубина целого числа — это количество списков, в которых оно находится. Например, вложенный список [1,[2,2],[[3],2],1] имеет значения каждого целого числа, установленные в его глубину. Верните сумму каждого целого числа в nestedList, умноженного на его глубину. Пример:

Input: nestedList = [1,[4,[6]]]
Output: 27
Explanation: One 1 at depth 1, one 4 at depth 2, and one 6 at depth 3. 1*1 + 4*2 + 6*3 = 27.

👨‍💻 Алгоритм: 1⃣ Инициализация и вызов рекурсивной функции: Создайте основную функцию, которая принимает вложенный список и вызывает вспомогательную рекурсивную функцию с начальной глубиной 1. 2⃣ Рекурсивное исследование списка: В вспомогательной функции пройдите по каждому элементу списка. Если элемент является целым числом, добавьте его значение, умноженное на текущую глубину, к общей сумме. Если элемент является списком, вызовите вспомогательную функцию рекурсивно с увеличенной глубиной. 3⃣ Возврат результата: Возвращайте общую сумму на каждом уровне рекурсии. Основная функция возвращает итоговую сумму. 😎 Решение:

class Solution:
    def depthSum(self, nestedList: List[NestedInteger]) -> int:
        def dfs(lst, depth):
            total = 0
            for nested in lst:
                if nested.isInteger():
                    total += nested.getInteger() * depth
                else:
                    total += dfs(nested.getList(), depth + 1)
            return total
        
        return dfs(nestedList, 1)

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

#medium Задача: 380. Insert Delete GetRandom O(1) Реализуйте класс RandomizedSet: RandomizedSet(): Инициализирует объект RandomizedSet. bool insert(int val): Вставляет элемент val в множество, если его там нет. Возвращает true, если элемент отсутствовал, и false в противном случае. bool remove(int val): Удаляет элемент val из множества, если он присутствует. Возвращает true, если элемент присутствовал, и false в противном случае. int getRandom(): Возвращает случайный элемент из текущего множества элементов (гарантируется, что по крайней мере один элемент существует при вызове этого метода). Каждый элемент должен иметь равную вероятность быть возвращенным. Вы должны реализовать функции класса таким образом, чтобы каждая функция работала в среднем за O(1) по времени. Пример:

Input
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
Output
[null, true, false, true, 2, true, false, 2]

👨‍💻 Алгоритм: 1⃣Создать словарь для хранения значений и их индексов, а также список для хранения значений. 2⃣Метод insert(val): Проверить наличие значения в словаре. Если отсутствует, добавить значение в список и обновить словарь с новым индексом. Метод remove(val): Проверить наличие значения в словаре. Если присутствует, заменить удаляемое значение последним элементом списка, обновить его индекс в словаре, удалить последний элемент из списка и удалить значение из словаря. 3⃣Метод getRandom(): Возвращать случайный элемент из списка, используя встроенную функцию генерации случайных чисел. 😎 Решение:

import random

class RandomizedSet:
    def __init__(self):
        self.dict = {}
        self.list = []

    def insert(self, val: int) -> bool:
        if val in self.dict:
            return False
        self.dict[val] = len(self.list)
        self.list.append(val)
        return True

    def remove(self, val: int) -> bool:
        if val not in self.dict:
            return False
        last_element = self.list[-1]
        index = self.dict[val]
        self.list[index] = last_element
        self.dict[last_element] = index
        self.list.pop()
        del self.dict[val]
        return True

    def getRandom(self) -> int:
        return random.choice(self.list)

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

Получите грант на обучение в Центральном университете Прояви себя, получи грант до 2,8 млн на обучение ИТ и бизнесу в вузе. Для школьников 10-х и 11-х классов, СПО. Подать заявку #реклама apply.centraluniversity.ru О рекламодателе

#medium Задача: 236. Lowest Common Ancestor of a Binary Tree Дано бинарное дерево. Найдите наименьший общий предок (LCA) двух заданных узлов в дереве. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Если текущий узел является одним из узлов p или q, установите переменную mid в значение True и продолжите поиск другого узла в левой и правой ветвях. 2⃣Проверка поддеревьев: Выполните рекурсивный обход левой и правой ветвей дерева. Если какая-либо из ветвей (левая или правая) возвращает True, это означает, что один из двух узлов найден ниже по дереву. 3⃣Определение LCA: Если в любой момент обхода дерева две из трех переменных (left, right или mid) становятся True, это означает, что найден наименьший общий предок (LCA) для узлов p и q. 😎 Решение:

class Solution:
    def __init__(self):
        self.ans = None

    def recurseTree(self, currentNode, p, q):
        if not currentNode:
            return False

        left = self.recurseTree(currentNode.left, p, q) ? 1 : 0
        right = self.recurseTree(currentNode.right, p, q) ? 1 : 0
        mid = (currentNode == p or currentNode == q) ? 1 : 0

        if mid + left + right >= 2:
            self.ans = currentNode

        return mid + left + right > 0

    def lowestCommonAncestor(self, root, p, q):
        self.recurseTree(root, p, q)
        return self.ans

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

#medium Задача: 379. Design Phone Directory Создайте телефонный справочник, который изначально имеет maxNumbers пустых слотов для хранения номеров. Справочник должен хранить номера, проверять, пуст ли определенный слот, и освобождать данный слот. Реализуйте класс PhoneDirectory: PhoneDirectory(int maxNumbers) Инициализирует телефонный справочник с количеством доступных слотов maxNumbers. int get() Предоставляет номер, который никому не назначен. Возвращает -1, если номера недоступны. bool check(int number) Возвращает true, если слот доступен, и false в противном случае. void release(int number) Перераспределяет или освобождает номер слота. Пример:

Input
["PhoneDirectory", "get", "get", "check", "get", "check", "release", "check"]
[[3], [], [], [2], [], [2], [2], [2]]
Output
[null, 0, 1, true, 2, false, null, true]

👨‍💻 Алгоритм: 1⃣Инициализировать массив isSlotAvailable размером maxNumbers, установив значение true во всех индексах. 2⃣Метод get(): Проходить по массиву isSlotAvailable. Если найдется true на каком-либо индексе, установить isSlotAvailable[i] = false и вернуть i. Если доступных слотов нет, вернуть -1. Метод check(number): Вернуть значение isSlotAvailable[number]. 3⃣Метод release(number): Установить isSlotAvailable[number] = true. 😎 Решение:

class PhoneDirectory:
    def __init__(self, maxNumbers):
        self.is_slot_available = [True] * maxNumbers

    def get(self):
        index = next((i for i, available in enumerate(self.is_slot_available) if available), -1)
        if index != -1:
            self.is_slot_available[index] = False
        return index

    def check(self, number):
        return self.is_slot_available[number]

    def release(self, number):
        self.is_slot_available[number] = True

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

#medium Задача: 235. Lowest Common Ancestor of a Binary Search Tree Дано бинарное дерево поиска (BST). Найдите наименьший общий предок (LCA) двух заданных узлов в BST. Согласно определению LCA на Википедии: "Наименьший общий предок определяется между двумя узлами p и q как наименьший узел в дереве T, который имеет как p, так и q в качестве потомков (где мы допускаем, что узел может быть потомком самого себя)." Пример:

Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
Output: 6
Explanation: The LCA of nodes 2 and 8 is 6.

👨‍💻 Алгоритм: 1⃣Начало обхода дерева с корня: Начните обход дерева с корневого узла. Проверьте, находятся ли узлы p и q в правом или левом поддереве текущего узла. 2⃣Продолжение поиска в поддереве: Если оба узла p и q находятся в правом поддереве текущего узла, продолжайте поиск в правом поддереве, начиная с шага 1. Если оба узла p и q находятся в левом поддереве текущего узла, продолжайте поиск в левом поддереве, начиная с шага 1. 3⃣Нахождение LCA: Если узлы p и q находятся в разных поддеревьях относительно текущего узла или один из узлов равен текущему узлу, то текущий узел является наименьшим общим предком (LCA). Верните этот узел как результат. 😎 Решение:

class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        parentVal = root.val
        pVal = p.val
        qVal = q.val

        if pVal > parentVal and qVal > parentVal:
            return self.lowestCommonAncestor(root.right, p, q)
        elif pVal < parentVal and qVal < parentVal:
            return self.lowestCommonAncestor(root.left, p, q)
        else:
            return root

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

Твое резюме на HeadHunter — ОК, если ты видишь это. HeadHunter сравнивает ключевые навыки в твоем резюме и в вакансии и в момент отклика отображает, насколько % ты соответствуешь требованиям. Специальный бейджик «Подходит по навыкам на 100%» отображается, если соответствие составляет более 60%. Если при просмотре вакансий ты видишь такой бейджик, это значит, что список навыков в твоем резюме качественно составлен. Это важный параметр, так как рекрутерам чаще показываются резюме с лучшим соответствием. О том, как правильно указывать ключевые навыки и оптимизировать свое резюме я уже рассказывал в этом видео

Ищем Python разработчиков. Релокейт, удалёнка, высокая зарплата! Вакансии с опытом и без. У нас только проверенные вакансии, вручную отбираем каждую👇 @it_match_python Больше не нужно тратить драгоценное время на поиск вакансий, подпишись!

#medium Задача: 378. Kth Smallest Element in a Sorted Matrix Дана матрица размером n x n, где каждая строка и каждый столбец отсортированы в порядке возрастания. Верните k-й наименьший элемент в матрице. Заметьте, что это k-й наименьший элемент в отсортированном порядке, а не k-й уникальный элемент. Вы должны найти решение с использованием памяти лучше, чем O(n²). Пример:

Input: matrix = [[-5]], k = 1
Output: -5

👨‍💻 Алгоритм: 1⃣Инициализировать мин-кучу H. В нашем решении мы будем рассматривать каждую строку как отдельный список. Поскольку столбцы также отсортированы, мы можем рассматривать каждый столбец как отдельный список. 2⃣Взять первые элементы из min(N, K) строк, где N представляет количество строк, и добавить каждый из этих элементов в кучу. Важно знать, к какой строке и столбцу принадлежит элемент, чтобы в дальнейшем перемещаться по соответствующему списку. 3⃣Мин-куча будет содержать тройки информации (значение, строка, столбец). Куча будет упорядочена по значениям, и мы будем использовать номера строк и столбцов для добавления следующего элемента, если текущий элемент будет удален из кучи. 😎 Решение:

import heapq

class Solution:
    def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
        
        N = len(matrix)
                minHeap = []
        for r in range(min(k, N)):
            
            minHeap.append((matrix[r][0], r, 0))
        
        heapq.heapify(minHeap)    
        
        while k:
            
            element, r, c = heapq.heappop(minHeap)
            
            if c < N - 1:
                heapq.heappush(minHeap, (matrix[r][c+1], r, c+1))
            
            k -= 1
        
        return element  

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

Высшее дистанционное образование в Росдистант Современный формат: обучение и экзамены онлайн! Бакалавриат 60000р! Государственный диплом Подать заявку #реклама 16+ rosdistant.ru О рекламодателе

#hard Задача: 472. Concatenated Words Дан массив строк words (без дубликатов). Верните все составные слова из данного списка слов. Составное слово определяется как строка, которая полностью состоит как минимум из двух более коротких слов (не обязательно различных) из данного массива. Пример:

Input: words = ["cat","cats","catsdogcats","dog","dogcatsdog","hippopotamuses","rat","ratcatdogcat"]
Output: ["catsdogcats","dogcatsdog","ratcatdogcat"]
Explanation: "catsdogcats" can be concatenated by "cats", "dog" and "cats"; 
"dogcatsdog" can be concatenated by "dog", "cats" and "dog"; 
"ratcatdogcat" can be concatenated by "rat", "cat", "dog" and "cat".

👨‍💻 Алгоритм: 1⃣Для каждого слова в списке: Построить неявный граф, в котором узлы представляют индексы символов в слове, а ребра представляют возможность перехода от одного индекса к другому, если подстрока между ними является словом из списка. 2⃣Использовать поиск в глубину (DFS) для проверки, можно ли достигнуть узел с индексом word.length от узла с индексом 0 в графе. 3⃣Если узел word.length достижим от узла 0, добавить слово в ответ. 😎 Решение:

class Solution:
    def dfs(self, word, length, visited, dictionary):
        if length == len(word):
            return True
        if visited[length]:
            return False
        visited[length] = True
        for i in range(len(word) - (1 if length == 0 else 0), length, -1):
            if word[length:i] in dictionary and self.dfs(word, i, visited, dictionary):
                return True
        return False

    def findAllConcatenatedWordsInADict(self, words):
        dictionary = set(words)
        answer = []
        for word in words:
            visited = [False] * len(word)
            if self.dfs(word, 0, visited, dictionary):
                answer.append(word)
        return answer

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

#medium Задача: 470. Implement Rand10() Using Rand7() Дано API rand7(), которое генерирует случайное целое число в диапазоне [1, 7]. Напишите функцию rand10(), которая генерирует случайное целое число в диапазоне [1, 10]. Вы можете вызывать только API rand7(), и не должны вызывать другие API. Пожалуйста, не используйте встроенные в язык функции для генерации случайных чисел. Каждый тестовый случай будет содержать один внутренний аргумент n, который указывает количество вызовов вашей реализованной функции rand10() во время тестирования. Обратите внимание, что это не аргумент, передаваемый в rand10(). Пример:

Input: n = 1
Output: [2]

😎 Решение:

class Solution:
    def rand10(self):
        while True:
            row = rand7()
            col = rand7()
            idx = col + (row - 1) * 7
            if idx <= 40:
                return 1 + (idx - 1) % 10

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

Помощь в трудоустройстве в IT-сфере! В России из-за дефицита айтишников запустили бесплатную программу по обучению IT-специалистов. Теперь любой желающий может попробовать себя в IT с полного нуля и начать обучение бесплатно! Узнайте про дальнейшее трудоустройство в ведущие IT-компании для восполнения кадрового дефицита. Для этого нужно: - Перейти по ссылке - Заполнить анкету и ответить на вопросы (занимает менее 3 минут) - На основании ваших ответов вы сразу узнаете, подходит ли вам сфера IT и сможете ли вы в ней работать Перейти на сайт #реклама 16+ urban-university.ru О рекламодателе

#medium Задача: 538. Convert BST to Greater Tree Дано корень бинарного дерева поиска (BST), преобразуйте его в дерево, в котором каждый ключ исходного BST изменен на исходный ключ плюс сумму всех ключей, больших исходного ключа в BST. Напоминаем, что бинарное дерево поиска — это дерево, удовлетворяющее следующим условиям: Левое поддерево узла содержит только узлы с ключами, меньшими ключа узла. Правое поддерево узла содержит только узлы с ключами, большими ключа узла. И левое, и правое поддеревья также должны быть бинарными деревьями поиска. Пример:

Input: root = [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

👨‍💻 Алгоритм: 1⃣Поддерживаем глобальное состояние, чтобы каждая рекурсивная функция могла получать и изменять текущую сумму. Проверяем существование текущего узла, рекурсивно обрабатываем правое поддерево. 2⃣Посещаем текущий узел, обновляем его значение и общую сумму. 3⃣Рекурсивно обрабатываем левое поддерево. 😎 Решение:

class Solution:
    def __init__(self):
        self.sum = 0

    def convertBST(self, root: TreeNode) -> TreeNode:
        if root:
            self.convertBST(root.right)
            self.sum += root.val
            root.val = self.sum
            self.convertBST(root.left)
        return root

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

Бесплатное IT-образование в 2024 Отобрали для вас полезные телеграм-каналы, которые помогут освоить программирование и другие IT-направления Выбирайте нужное и подписывайтесь: 👩‍💻 Python: @PythonPortal 📱 GitHub: @git_developer 👩‍💻 Frontend: @FrontendPortal 🤓 Книги айти: @portalToIT 👩‍💻 Java: @Java_Iibrary 👩‍💻 C#: @KodBlog 👩‍💻 С/С++: @Cpportal ⚙️ Backend: @BackendPortal 🐞 Тестирование: @QAPortal 👩‍💻 DevOps: @loose_code 🖥 Базы Данных & SQL: @SQL 👩‍💻 Golang: @juniorGolang 👩‍💻 PHP: @PHPortal 👩‍💻 Моб. разработка: @MobDev 👩‍💻 Разработка игр: @GameDevgx 🖥 Data Science: @DataSciencegx 🤔 Хакинг & ИБ: @cybersecinform 📱 Маркетинг: @MarketingPortal 🖥 Дизайн: @PortalToDesign ➡️ Сохраняйте себе, чтобы не потерять

#easy Задача: 338. Counting Bits Дано целое число n, верните массив ans длиной n + 1, такой что для каждого i (0 <= i <= n), ans[i] будет равняться количеству единиц в двоичном представлении числа i. Пример:

Input: n = 5
Output: [0,1,1,2,1,2]
Explanation:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

👨‍💻 Алгоритм: 1⃣ Инициализация массива: Создайте массив ans длиной n + 1, заполненный нулями. Этот массив будет содержать количество единиц в двоичном представлении каждого числа от 0 до n. 2⃣ Итерация и вычисление: Пройдите в цикле по всем числам от 1 до n. Для каждого числа x используйте битовую операцию x & (x - 1), чтобы убрать последнюю установленную биту, и добавьте 1 к значению ans для этого результата. Это количество единиц в двоичном представлении числа x. 3⃣ Возврат результата: Верните заполненный массив ans, который содержит количество единиц для каждого числа от 0 до n. 😎 Решение:

class Solution:
    def countBits(self, num: int) -> List[int]:
        ans = [0] * (num + 1)
        for x in range(1, num + 1):
            ans[x] = ans[x & (x - 1)] + 1
        return ans

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

5 причин, почему вам нужен Битрикс24 Мессенджер + AI 1) Ничего личного. Никаких Алена-ноготочки и любимая жена 2) Только рабочее. Общение с коллегами в чатах, каналах и тредах. 3) Слова становятся делами. Задачи и встречи ставятся прямо из переписки в чате. 4) Синки. Мгновенные видеоколлы до 100 человек из чата в один клик. 5) Нейросеть. Можно прямо в групповом чате штурмить идеи с AI-помощником. А, последняя причина – пользоваться можно бесплатно. Забирайте бесплатный мессенджер для работы компании — Битрикс24 Попробовать #реклама 16+ bitrix24.ru О рекламодателе

#medium Задача: 468. Validate IP Address Допустимый IPv4-адрес — это IP в форме "x1.x2.x3.x4", где 0 <= xi <= 255 и xi не может содержать ведущие нули. Например, "192.168.1.1" и "192.168.1.0" являются допустимыми IPv4-адресами, тогда как "192.168.01.1", "192.168.1.00" и "192.168@1.1" являются недопустимыми IPv4-адресами. Допустимый IPv6-адрес — это IP в форме "x1:x2:x3:x4:x5:x6:x7 ", где: 1 <= xi.length <= 4 xi — это шестнадцатеричная строка, которая может содержать цифры, строчные английские буквы ('a' до 'f') и прописные английские буквы ('A' до 'F'). Ведущие нули в xi допускаются. Пример:

Input: queryIP = "172.16.254.1"
Output: "IPv4"
Explanation: This is a valid IPv4 address, return "IPv4".

👨‍💻 Алгоритм: 1⃣Для проверки адреса IPv4: Разделить IP на четыре части по разделителю ".". Проверить каждую подстроку: Является ли она целым числом между 0 и 255. Не содержит ли она ведущих нулей (исключение — число "0"). 2⃣Для проверки адреса IPv6: Разделить IP на восемь частей по разделителю ":". Проверить каждую подстроку: Является ли она шестнадцатеричным числом длиной от 1 до 4 символов. 3⃣Если IP не соответствует ни одному из форматов, вернуть "Neither". 😎 Решение:

class Solution:
    def validateIPv4(self, IP: str) -> str:
        nums = IP.split(".")
        for x in nums:
            if len(x) == 0 or len(x) > 3:
                return "Neither"
            if x[0] == '0' and len(x) != 1:
                return "Neither"
            if not x.isdigit():
                return "Neither"
            if int(x) > 255:
                return "Neither"
        return "IPv4"

    def validateIPv6(self, IP: str) -> str:
        nums = IP.split(":")
        hexdigits = "0123456789abcdefABCDEF"
        for x in nums:
            if len(x) == 0 or len(x) > 4:
                return "Neither"
            for ch in x:
                if ch not in hexdigits:
                    return "Neither"
        return "IPv6"

    def validIPAddress(self, IP: str) -> str:
        if IP.count(".") == 3:
            return self.validateIPv4(IP)
        elif IP.count(":") == 7:
            return self.validateIPv6(IP)
        else:
            return "Neither"

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

#medium Задача: 337. House Robber III Вор снова нашел себе новое место для краж. В этом районе есть только один вход, который называется корнем. Кроме корня, каждый дом имеет только один родительский дом. После осмотра, умный вор понял, что все дома в этом месте образуют бинарное дерево. Полиция будет автоматически уведомлена, если два дома, напрямую связанные между собой, будут ограблены в одну ночь. Дано корневое дерево бинарного дерева, верните максимальную сумму денег, которую вор может украсть, не уведомляя полицию. Пример:

Input: root = [3,4,5,1,3,null,1]
Output: 9
Explanation: Maximum amount of money the thief can rob = 4 + 5 = 9.

👨‍💻 Алгоритм: 1⃣ Инициализация и базовый случай: Создайте вспомогательную функцию helper, которая принимает узел в качестве входных данных и возвращает массив из двух элементов, где первый элемент представляет максимальную сумму денег, которую можно украсть, если не грабить этот узел, а второй элемент - если грабить этот узел. Базовый случай для вспомогательной функции - узел null, и в этом случае функция возвращает массив из двух нулей [0, 0]. 2⃣ Рекурсивное исследование дерева: В функции helper вызывайте её рекурсивно для левого и правого поддеревьев текущего узла. Если грабить текущий узел, то нельзя грабить его потомков, поэтому сумма будет равна значению текущего узла плюс максимальные суммы для случаев, когда потомки не грабятся. Если не грабить текущий узел, то можно свободно выбирать, грабить потомков или нет, поэтому сумма будет равна максимальной сумме из двух вариантов для каждого потомка. 3⃣ Возврат результата: В основной функции rob вызовите helper для корня дерева и верните максимальное значение из двух элементов массива, возвращенного функцией helper. 😎 Решение:

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

class Solution:
    def rob(self, root: TreeNode) -> int:
        def helper(node):
            if not node:
                return (0, 0)
            left = helper(node.left)
            right = helper(node.right)
            rob = node.val + left[1] + right[1]
            not_rob = max(left) + max(right)
            return (rob, not_rob)
        
        answer = helper(root)
        return max(answer)

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