Как определить количество листьев на самом низком уровне полного двоичного дерева?

Question

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

Для Например, если бы у меня было следующее полное двоичное дерево,

      _ 7_
    /      \
   4        9
  / \     / \
 2   6   8   10
/ \  /
1  3 5

, алгоритм вернул бы «3», поскольку на самом нижнем уровне дерева есть три листа.

Я был смог найти множество решений для подсчета всех листьев в обычных или сбалансированных двоичных деревьях, но пока мне не повезло с конкретным случаем нахождения количества листьев на самом низком уровне бинарного дерева полного . Любая помощь приветствуется.

Answer 1

Выполните поиск в ширину, чтобы вы также могли найти несколько узлов на каждом уровне.

Какой-то псевдокод

q <- new queue of (node, level) data
add (root, 0) in q

nodesPerLevel <- new vector of integers 

while q is not empty:
    (currentNode, currentLevel) <- take from top of q
    nodesPerLevel[currentLevel] += 1
    for each child in currentNode's children: 
        add (child, currentLevel + 1) in q

return last value of nodesPerLevel