我一直在搜索，但没能找到与我的问题类似的内容。也许我只是没有正确搜索。无论如何，这是我的考试复习中的一个问题。给定一棵二叉树，我需要输出一个列表，使得列表中的每个项目都是项目列表索引处二叉树中某个级别上的节点数。我的意思是，lst = [1,2,1]，第 0 个索引是树中的第 0 层，1 是该层中有多少个节点。 lst[1] 将代表第 1 级该二叉树中的节点数 (2)。不保证该树是平衡的。我们只学习了前序、中序和后序遍历，但我看不出它们在这个问题中有何用处。我不是在要求特定的代码，只是关于如何解决这个问题或背后的逻辑的想法。感谢您的帮助。
最佳答案
只要您只对每个节点计数一次，搜索顺序并不重要。具有递归的深度优先搜索解决方案是:
- 创建一个 map
counters来存储每个级别的计数器。例如。counters[i]是目前在i层找到的节点数。假设 0 级是根。 - 定义一个递归函数
count_subtree(node, level):递增counters[level]一次。然后对于给定节点的每个子节点，调用count_subtree(child, level + 1)(子节点处于更深一层)。 - 调用
count_subtree(root_node, 0)从根开始计数。这将导致count_subtree在每个节点上只运行一次，因为每个节点只有一个父节点，因此counters[level]将每个节点递增一次。叶节点是基本情况(没有子节点可以调用递归函数)。 - 根据计数器的值构建您的最终列表，按它们的键升序排列。
这适用于任何类型的树，而不仅仅是二叉树。运行时间为 O(树中的节点数)。旁注:深度优先搜索解决方案比类似的广度优先搜索解决方案更容易在并行处理器或机器上划分和运行。
关于python - 计算二叉树中每个级别的节点数，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/49909109/