Maximum Depth of Binary Tree

Лёгкая№104узлы дерева

Дан корень двоичного дерева. Нужно найти его глубину: сколько узлов на самом длинном пути от корня вниз до листа. Наше дерево: 11 с потомками 4 и 8; у 8 потомки 2 и 13; у 2 левый потомок 6 — ответ 4: путь 11 → 8 → 2 → 6.

104 Maximum Depth of Binary TreeРазбор · 1×

Пример: найти глубину кривого двоичного дерева: первый лист неглубоко, а самый глубокий — далеко справа.

nonenonenonenonenonenonenone11482136стек вызововвершина справа11
ещё не посещёнждёт в стеке вызововтекущий вызоввернул, ↑ его глубинаnone: пустой потомок

11 — узел, а не none

01/43
сначала · назад · пуск · шаг
Скорость
1function maxDepth(node):
2 if node is none:
3 return 0
4 left = maxDepth(node.left)
5 right = maxDepth(node.right)
6 return 1 + max(left, right)
состояние
node
11
left
–
right
–
нажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Глубина дерева — это корень плюс глубина его более глубокого поддерева, а каждое поддерево — такое же дерево поменьше, поэтому хватает одного вызова на узел.
  2. Узел отвечает только после того, как ответили обе его стороны, поэтому первый найденный лист, 4, ничего не решает в одиночку: корень сравнивает 1 и 3.
  3. Пустой потомок возвращает 0, и лист получает 1 + max(0, 0) = 1 без отдельной проверки.

Сложность

Время O(n): по одному вызову на узел и на каждого пустого потомка. Память O(h), где h — высота дерева: в стеке вызовов лежит один путь от корня.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.