Maximum Depth of Binary Tree

Q: Какова временная сложность задачи «Максимальная глубина бинарного дерева»?

Каждый подход посещает каждый узел один раз, поэтому временная сложность составляет O(n) . В версиях с поиском в глубину используется O(h) дополнительной памяти для текущего пути, где h — глубина. В версии с поиском в ширину используется O(w) памяти для самого широкого уровня — примерно половины узлов полного дерева.

Q: Следует ли использовать DFS или BFS для определения максимальной глубины бинарного дерева?

Оба алгоритма выполняются за время O(n) . Поиск в глубину короче в записи и использует объём памяти, пропорциональный глубине, поэтому подходит для широких неглубоких деревьев. Поиск в ширину напрямую подсчитывает уровни и использует объём памяти, пропорциональный ширине самого широкого уровня, поэтому подходит для глубоких узких деревьев. Для нахождения минимальной глубины выигрывает BFS, поскольку он может остановиться на первом листе.

Q: В чём разница между глубиной и высотой бинарного дерева?

Глубина узла — это число шагов от корня до него; высота — число шагов от него до самого глубокого листа. Максимальная глубина дерева равна высоте корня. В этой задаче считаются узлы, поэтому глубина единственного узла равна 1 ; если считать рёбра, получится на единицу меньше.

ЛегкоОбход деревьев

+10

Дано бинарное дерево, хранящееся в массиве tree в порядке уровней. Корень находится по индексу 0, потомки узла с индексом i находятся по индексам 2*i+1 (слева) и 2*i+2 (справа), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1. Верните максимальную глубину дерева: количество узлов в самом длинном пути от корня до листа.

Функция

maxDepth(tree: integer-array) → integer

treeinteger-array: двоичное дерево в порядке уровней, где -1 обозначает пустое место
Возвращаетinteger: количество узлов в самом длинном пути от корня до листа

Ограничения

1 ≤ tree.length ≤ 32767
Каждый элемент tree[i] — это -1 или значение, удовлетворяющее условию 0 ≤ tree[i] ≤ 1000.
tree[0] никогда не равно -1, поэтому в дереве есть как минимум один узел.
После последнего узла в массиве могут идти дополнительные элементы -1.
Оба потомка пустого узла тоже пусты, а глубина не превышает 14.

Примеры

Ввод: tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]
Вывод: 4
Пояснение: Самый длинный путь — 5, 8, 3, 6 (индексы 0, 1, 4, 9), он содержит 4 узла. Путь через 1 заканчивается после 2 узлов.

Ввод: tree = [7, -1, -1]
Вывод: 1
Пояснение: Две записи -1 обозначают пустые места для потомков корня. Сам корень — это путь из одного узла, поэтому глубина равна 1, а не 0.

Ввод: tree = [2, -1, 9, -1, -1, -1, 4]
Вывод: 3
Пояснение: У корня 2 нет левого потомка. Его правый потомок 9 с индексом 2 имеет 4 с индексом 6 в качестве правого потомка — путь из 3 узлов.

Дополнительный вопрос

Как бы вы вернули значения на самом длинном пути от корня до листа, а также его длину? Если несколько путей одинаковой длины, какой из них вы бы вернули?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Глубина определяется самой длинной ветвью, и нельзя узнать, какая именно ветвь самая длинная, не посетив каждый узел. Поэтому нужен полный обход, который определяет глубину на каждом узле. Рекурсия, поиск в ширину по уровням и поиск в глубину с собственным стеком выполняют это за один проход.

Рекурсия в двух поддеревьях

Идея

Место дочернего узла считается существующим, если его индекс находится внутри массива, а его значение не равно -1. Самый длинный путь через узел спускается в его более глубокое поддерево, поэтому глубина для индекса i равна 1 для самого узла плюс наибольшая из глубин для 2*i+1 и 2*i+2. У пустого места глубина равна 0 — это завершает рекурсию. Для листа получается 1 + max(0, 0) = 1, а значения поднимаются обратно к корню.

Каждый узел посещается один раз. Стек вызовов хранит по одному фрейму на каждый уровень текущего пути, O(h), здесь не более 14.

Алгоритм

Напишите depth(i): если i находится за концом массива или tree[i] равно -1, верните 0.
В противном случае верните 1 + max(depth(2*i+1), depth(2*i+2)).
Верните depth(0).

def maxDepth(tree):
    def depth(i):
        # An index past the end or a -1 is an empty spot: depth 0.
        if i >= len(tree) or tree[i] == -1:
            return 0
        return 1 + max(depth(2 * i + 1), depth(2 * i + 2))

    return depth(0)

Поиск в ширину, уровень за уровнем

Идея

Максимальная глубина — это количество уровней, поэтому можно считать уровни, а не проходить по путям. Очередь посещает узлы в порядке уровней. Перед каждой обработкой считай размер очереди: эти узлы относятся ровно к одному уровню, потому что добавленные во время обработки дочерние узлы встают за ними. Каждая обработка увеличивает глубину на 1. В первом примере обрабатываются группы [5], [8, 1], [3] и [6], поэтому ответ — 4.

Очередь хранит по одному уровню за раз — O(w) для самого широкого уровня. В полном дереве глубины 14 это 8192 из 16383 узлов.

Алгоритм

Поместите корневой индекс 0 в очередь и задайте depth = 0.
Пока очередь не пуста, прибавляйте 1 к depth и считывайте размер очереди.
Извлеките столько индексов. Для каждого добавьте в очередь дочерние индексы 2*i+1 и 2*i+2, которые находятся внутри массива и не равны -1.
Когда очередь опустеет, верните depth.

from collections import deque


def maxDepth(tree):
    n = len(tree)
    queue = deque([0])
    depth = 0
    while queue:
        depth += 1
        for _ in range(len(queue)):  # exactly the nodes of this level
            i = queue.popleft()
            for child in (2 * i + 1, 2 * i + 2):
                if child < n and tree[child] != -1:
                    queue.append(child)
    return depth

Поиск в глубину с явным стеком

Идея

Храни собственный стек пар: индекс узла и его глубину, поскольку ничто другое не запоминает, насколько глубоко находится узел. Начни с (0, 1) — корня на глубине 1. Каждый узел помещается в стек один раз вместе с длиной пути до него, поэтому наибольшая глубина извлечённого узла и будет ответом. В первом примере 6 помещается в стек как (9, 4).

В стеке хранится примерно по одному ожидающему узлу-соседу на каждом уровне, O(h), и нет стека вызовов, который мог бы переполниться. Тот же код работает с деревом на указателях любой глубины.

Алгоритм

Поместите (0, 1) в стек и задайте best = 0.
Извлеките пару (i, depth) и задайте best равным большему из best и depth.
Для каждого дочернего индекса 2*i+1 и 2*i+2, который находится в пределах массива и не равен -1, поместите его в стек с depth + 1.
Повторяйте, пока стек не опустеет, затем верните best.

def maxDepth(tree):
    n = len(tree)
    best = 0
    stack = [(0, 1)]  # (node index, depth of that node); the root is never empty
    while stack:
        i, depth = stack.pop()
        best = max(best, depth)
        for child in (2 * i + 1, 2 * i + 2):
            if child < n and tree[child] != -1:
                stack.append((child, depth + 1))
    return best

Ловушки и крайние случаи

Подсчёт рёбер вместо узлов. [7, -1, -1] имеет глубину 1, а не 0.
Пропуск проверки границ. В первом примере у 6 с индексом 9 дочерние индексы 19 и 20, которые выходят за пределы массива. Проверьте child < n перед чтением tree[child].
Вычисление глубины по длине массива. Хвостовые элементы -1 достигают уровня, на котором нет узла: [7, -1, -1] имеет длину 3, но глубину 1.
Чтение размера очереди внутри цикла обработки пакета. Добавленные во время обработки пакета дочерние узлы изменяют его, поэтому сначала сохраните размер.
Путаница со смещением в Lua и R, где индексация массивов начинается с 1. Используйте для индексов узлов нумерацию с 0, чтобы получить 2*i+1, и читайте tree[i + 1].

Частые вопросы3

Какова временная сложность задачи «Максимальная глубина бинарного дерева»?

Каждый подход посещает каждый узел один раз, поэтому временная сложность составляет O(n). В версиях с поиском в глубину используется O(h) дополнительной памяти для текущего пути, где h — глубина. В версии с поиском в ширину используется O(w) памяти для самого широкого уровня — примерно половины узлов полного дерева.

Следует ли использовать DFS или BFS для определения максимальной глубины бинарного дерева?

Оба алгоритма выполняются за время O(n). Поиск в глубину короче в записи и использует объём памяти, пропорциональный глубине, поэтому подходит для широких неглубоких деревьев. Поиск в ширину напрямую подсчитывает уровни и использует объём памяти, пропорциональный ширине самого широкого уровня, поэтому подходит для глубоких узких деревьев. Для нахождения минимальной глубины выигрывает BFS, поскольку он может остановиться на первом листе.

В чём разница между глубиной и высотой бинарного дерева?

Глубина узла — это число шагов от корня до него; высота — число шагов от него до самого глубокого листа. Максимальная глубина дерева равна высоте корня. В этой задаче считаются узлы, поэтому глубина единственного узла равна 1; если считать рёбра, получится на единицу меньше.

def maxDepth(tree):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

tree = [5, 8, 1, -1, 3, -1, -1, -1, -1, 6]

Ожидаемый вывод

Maximum Depth of Binary Tree

Функция

Ограничения

Примеры

Подсказки

Решение

Рекурсия в двух поддеревьях

Поиск в ширину, уровень за уровнем

Поиск в глубину с явным стеком

Ловушки и крайние случаи

Частые вопросы3

Похожие задачи