Maximum Depth of Binary Tree

Сначала разберёмся, как перемещаться по массиву. У узла с индексом i левый потомок находится по индексу 2*i+1, а правый — по индексу 2*i+2. Потомок существует, только если его индекс находится в пределах массива и значение по этому индексу не равно -1. В массиве [5, 8, 1, -1, 3, -1, -1, -1, -1, 6] у корня 5 потомки находятся по индексам 1 и 2, у узла 8 с индексом 1 левая позиция 3 пуста, а справа от него, по индексу 4, находится узел 3; ниже этого узла 3 находится узел 6 с индексом 9.

Теперь разберём идею. Самый длинный путь через узел идёт вниз по тому из двух поддеревьев, которое глубже. Поэтому глубина поддерева с корнем в узле с индексом i равна 1 для самого узла плюс большая из глубин поддеревьев с корнями в узлах 2*i+1 и 2*i+2. Пустая позиция имеет глубину 0, что завершает рекурсию. Глубина листа равна 1 + max(0, 0) = 1, а значения возвращаются вверх к корню.

Каждый узел посещается один раз, поэтому время работы составляет O(n). В стеке вызовов хранится по одному кадру на каждый уровень текущего пути — O(h), где h — глубина; здесь она не превышает 14. Именно это ограничение делает рекурсию безопасной в этой задаче. В дереве на указателях, имеющем форму длинной цепочки, тот же код достиг бы предела рекурсии, который в Python составляет 1000 кадров.

Максимальная глубина — это количество уровней в дереве, поэтому можно считать уровни, а не проходить по путям. Очередь посещает узлы в порядке уровней: сначала поместите в неё корень, а затем каждый раз, когда извлекаете узел, добавляйте его существующих потомков в конец очереди.

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

Каждый узел один раз попадает в очередь и один раз извлекается из неё; временная сложность — O(n). В очереди одновременно находится один уровень; пространственная сложность для самого широкого уровня w — O(w). В полном дереве на нижнем уровне находится примерно половина узлов: 8192 из 16383 при глубине 14.

Ты можешь проходить по путям, как это делает рекурсия, не выполняя ни одного рекурсивного вызова. Используй собственный стек и храни каждый узел вместе с его глубиной, поскольку ничто другое не запоминает, насколько глубоко он находится. Начни с пары (0, 1): корня на глубине 1.

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

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