计算二进制文件中每个级别的节点数

Question

我已经搜索了一点，但没有找到任何类似我的问题。也许我只是没有正确地搜索。不管怎样，这是我考试复习中的一个问题。给定一个二叉树，我需要输出一个列表，使列表中的每个项都是项目列表索引处二叉树中某一级别上的节点数。我的意思是，lst=[1,2,1]，第0个索引是树中的第0个级别，1是该级别中有多少个节点。lst[1]将表示该二叉树中1级节点的数目（2）。这棵树不能保证是平衡的。我们只学习了前序遍历，序遍历和后序遍历，我看不出它们在这个问题上有什么用处。我不是在问具体的代码，只是想知道我该如何解决这个问题或者背后的逻辑。感谢任何帮助。在

Answer 1

搜索顺序并不重要，只要你只对每个节点计数一次。具有递归的深度优先搜索解决方案是：

• 创建一个映射counters，为每个级别存储一个计数器。E、 g.counters[i]是到目前为止在i级别找到的节点数。假设0级是根。在
• 定义一个递归函数count_subtree(node, level)：增量counters[level]一次。然后，对于给定节点的每个子节点，调用count_subtree(child, level + 1)（子节点在1层以上）。在
• 调用count_subtree(root_node, 0)从根开始计数。这将导致count_subtree在每个节点上只运行一次，因为每个节点只有一个父节点，因此counters[level]将在每个节点上递增一次。叶节点是基本情况（没有子节点可以调用递归函数）。在
• 根据计数器的值，按其键升序排列，构建最终列表。在

这将适用于任何类型的树，而不仅仅是二进制。运行时间是O（树中的节点数）。旁注：深度优先搜索解决方案比类似的广度优先搜索解决方案更容易划分并在并行处理器或机器上运行。在