你如何找到完整二叉树最低层的叶子数？

Question

我正在尝试定义一种算法，该算法 return 是完整二叉树最低级别的叶子数。完全二叉树，我的意思是一棵二叉树，它的每一层，除了最后一层，都被填充，最后一层的所有节点都尽可能地靠左。

例如，如果我有下面的完全二叉树，

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

算法会 return '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

你如何找到完整二叉树最低层的叶子数？

How do you find the number of leaves at the lowest level of a complete binary tree?

binary-tree