Подсчет узлов, равных среднему значению поддерева: ПРОСТОЕ РЕШЕНИЕ | LEETCODE 2265 | Решение за с...

Задача "Количество узлов, равное среднему значению поддерева" — это задача о бинарном дереве средней сложности, встречающаяся на реальных собеседованиях: обход в глубину (DFS), вычисление суммы и количества узлов поддерева, проверка среднего значения в каждом узле. Задача LeetCode: https://leetcode.com/problems/count-n... Решение (Java / Python / C++ / C): https://github.com/Shaanworkspace/YOU... Присоединяйтесь к сообществу: Telegram: https://t.me/opentech_shaanlabs WhatsApp: https://chat.whatsapp.com/CvlyO3ZBBoT... Задача LeetCode 2265 «Подсчет узлов, равных среднему значению поддерева» требует вернуть количество узлов, значение которых равно среднему значению поддерева. Метод перебора многократно пересчитывает суммы поддеревьев — время O(n²). Оптимальный подход использует однократный поиск в глубину в обратном порядке, возвращая пары (сумма, количество) — время O(n), пространство O(h). В этом видео рассматриваются оба подхода с примерами и кодом на Java, Python, C++ и C. 00:00 — Почему большинство людей не справляются с этой задачей о бинарном дереве Меня зовут Шан. Я позабочусь о том, чтобы вы правильно поняли вопрос, о чем в нем спрашивается, и вы поняли сначала метод перебора, а затем оптимизированный подход. 00:40 — Определение поддерева и как вычислить среднее значение Начнем с вопроса. Поддерево узла — это сам узел плюс все узлы, которые находятся ниже него. Мне нужна сумма для вычисления среднего значения, а затем его целочисленное значение. 02:33 — Пример: проверка значений и среднего значения Поддерево из нуля равно нулю. Поддерево из шести равно шести. Для узла четыре сумма равна 4 + 8 + 5 + 0 + 1 + 6 = 24, количество равно 6, среднее равно 4. Для узла пять сумма равна 5 + 6 = 11, количество равно 2, среднее равно 5. 04:49 — Метод перебора: пересчет каждого поддерева Давайте перейдем к методу перебора. Для каждого узла я буду вычислять среднее значение его поддерева, проходя по всем потомкам с нуля. 07:08 — Почему метод перебора терпит неудачу: узлы, проходящие многократно Давайте посмотрим на проблему. Ноль проходится три раза. Мы проходим без необходимости. Временная сложность составляет O(n²). Интервьюер не будет доволен этим. 09:28 — Оптимальный подход: поиск в глубину в обратном порядке возвращает пары В методе перебора нам нужна сумма и количество. Правое поддерево дает свою сумму и количество. Снизу вверх я прохожу только один раз. 10:13 — Обход снизу вверх передает сумму и количество вверх Что нужно передать снизу вверх, так это сумму и количество. Я просто передам сумму и количество каждого поддерева верхнему. Давайте посмотрим подробнее. 12:55 — Пробный запуск: отслеживание каждого листа узла до корня Восемь узлов спросят у своих потомков, какова сумма и количество левого узла, какова сумма и количество правого узла. Затем вычислят свою сумму и количество, проверят среднее значение и перейдут вверх. 15:55 — Почему один проход лучше, чем несколько Мне нужно идти только вверх, а не вниз три раза. Я прохожу только один раз. Каждый узел посещается ровно один раз. 16:57 — Псевдокод: функция DFS, возвращающая два значения Перейдем к псевдокоду. Вызовите функцию, сначала вычислите значение слева, затем значение справа. Если среднее значение равно значению узла, увеличьте ответ. 21:41 — Отправка и проверка: все тестовые случаи пройдены Давайте нажмем «Отправить» и посмотрим. Все тестовые случаи пройдены. У меня серия из 67 успешных попыток против 8. 22:31 — Итоговая сложность и подписка Время O(n), пространство O(h). Подпишитесь на канал, если вам понравилось видео. Поделитесь с другом, которому это больше всего нужно. Часто задаваемые вопросы В1: Что означает «Количество узлов равно среднему значению поддерева»? О1: Для каждого узла вычислите среднее значение всех значений в его поддереве (узел плюс потомки). Подсчитайте узлы, где значение равно этому среднему значению, округленному в меньшую сторону. В2: Что такое метод перебора и почему он медленный? О2: Пересчитайте всю сумму поддерева с нуля для каждого узла. Это означает, что одни и те же узлы посещаются несколько раз — время O(n в квадрате). В3: Как работает оптимальное решение DFS? О3: Обход в обратном порядке (пост-порядковый обход), возвращающий пары (сумма, количество). На каждом узле объединяются левая и правая пары, вычисляются сумма и количество, проверяется условие среднего значения, и результат передается вверх. Время O(n) — каждый узел посещен один раз. В4: Какова временная и пространственная сложность? О4: Время O(n) — каждый узел посещен один раз. Пространство для стека рекурсии O(h). Сбалансированное дерево O(log n), асимметричное дерево O(n). В5: Почему важен пост-порядковый обход? О5: Дочерние узлы обрабатываются раньше родительского, поэтому при обработке узла у нас уже есть суммы и количества поддеревьев — именно то, что нам нужно. В6: Какие задачи...