Count Complete Tree Nodes

Средняя№222узлы дерева

Дан корень полного двоичного дерева: все уровни заполнены, кроме, может быть, последнего, а последний заполнен слева. Нужно посчитать узлы быстрее, чем обойдя каждый. В нашем дереве 4 уровня: первые три заполнены, а на последнем 5 узлов из 8 — ответ 12.

222 Count Complete Tree NodesРазбор · 1×

Пример: посчитать узлы полного двоичного дерева: там, где левый и правый края одной длины, поддерево совершенное, и число узлов в нём известно сразу.

123456789101112стек вызововвершина справа1
ещё не посчитанждёт в стеке вызововтекущий вызовкрай, по которому идёмпосчитан, ↑ что вернул его вызов

1 — узел, а не none

01/38
сначала · назад · пуск · шаг
Скорость
1function countNodes(node):
2 if node is none:
3 return 0
4 hl = nodes down the left edge from node
5 hr = nodes down the right edge from node
6 if hl == hr:
7 return 2^hl - 1 // perfect: no need to go inside
8 return 1 + countNodes(node.left) + countNodes(node.right)
состояние
node
1
hl
–
hr
–
нажмите шаг, чтобы вернуться

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

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

  1. В полном дереве последний уровень заполняется слева. Если самый левый и самый правый пути одной длины, то и этот уровень заполнен, а в совершенном дереве из h уровней 2^h − 1 узлов.
  2. Если длины разные, хотя бы одно из двух поддеревьев совершенное, и один из двух вызовов отвечает сразу по своим краям. По частям считаем только вдоль одного пути вниз.

Сложность

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

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

Решить на LeetCode ↗

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