Где применяется
1. Задача
Вызовы рекурсивной функции ветвятся: один вызов делает два, каждый из них ещё два. Теперь ветвиться будут сами данные. У каждого элемента может быть несколько детей, а не один «следующий», как в связном списке.
Пример такой структуры: папки на компьютере. В верхней папке лежат файлы и другие папки, в тех ещё папки, и так до самого низа. Первыми обычно задают два вопроса: сколько всего элементов внутри и насколько глубоко они вложены. Программе резервного копирования нужно число файлов. Линтеру (программе, которая проверяет проект на ошибки и плохие привычки) нужна глубина, чтобы предупредить, если папки вложены на десять уровней.
Такая ветвящаяся структура называется деревом. Каждый элемент дерева это узел: в нём лежит значение и ссылки на детей. Единственный узел наверху, у которого нет родителя, это корень. Узел без детей это лист. В этом уроке дерево бинарное: у каждого узла не больше двух детей, left и right. Узел выглядит как { val, left, right }, а если ребёнка нет, на его месте null.
Обходить дерево в определённом порядке будем в следующем уроке. Сначала два самых простых измерения: размер (сколько узлов) и высота (сколько уровней). Оба считаются одним и тем же способом.
Этот шаг из платной части
Бесплатные шаги в начале курса (их 33) открыты всем: урок, задача и тесты. Этот шаг открывается с полным доступом. Начни с бесплатного аккаунта и бесплатных шагов.
Завести бесплатный аккаунтПосмотреть, что входитНа LeetCode
Задачи на двоичное дерево, где нужно измерить его целиком, например глубину или число узлов. Дай ответ для пустого дерева, потом сложи ответы левого и правого поддеревьев.
height из урока под другим именем.
countNodes из урока проходит как есть, а то, что дерево полное, позволяет потом попробовать более быстрый приём.
Как height, только с min вместо max, но у узла с одним ребёнком пустую сторону считать нельзя.
Тот же height, только вместо left и right цикл по списку детей.