如何统计二叉树各层级节点数量并输出对应列表？

嘿，这个问题我刷题的时候刚好碰过！其实核心就是统计二叉树每一层的节点数量，用BFS或者DFS都能轻松解决，我给你详细说下两种实现思路：

方法一：广度优先搜索（BFS） #

BFS的特性就是按层级遍历二叉树，完全贴合我们的需求。具体思路是用队列来维护当前层的所有节点，每次处理完一层就记录该层的节点数，再把下一层的节点加入队列。

具体步骤：

• 如果输入的二叉树是空的，直接返回空列表
• 初始化一个队列，把根节点放进去
• 创建一个空的结果列表用来存每层节点数
• 循环处理队列直到为空：
  • 先记录当前队列的长度，这就是当前层的节点数量
  • 把这个数量添加到结果列表里
  • 遍历当前层的每个节点，把它们存在的左、右子节点依次加入队列
• 最后返回结果列表

代码示例（Python） #

from collections import deque

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_count(root):
    if not root:
        return []
    result = []
    queue = deque([root])
    while queue:
        level_size = len(queue)
        result.append(level_size)
        # 遍历当前层的所有节点，把下一层节点加入队列
        for _ in range(level_size):
            node = queue.popleft()
            if node.left:
                queue.append(node.left)
            if node.right:
                queue.append(node.right)
    return result

# 测试你说的示例场景：输出 [1,2,1]
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)  # 第二层只有1个节点
print(level_order_count(root))  # 输出: [1, 2, 1]

方法二：深度优先搜索（DFS） #

如果更喜欢递归写法，DFS也能实现。我们可以在递归遍历的时候记录当前节点所在的层级，动态更新对应层级的节点计数。

具体思路：

• 初始化一个空的结果列表
• 定义一个递归辅助函数，参数是当前节点和当前层级
• 如果当前节点为空，直接返回
• 如果当前层级等于结果列表的长度，说明这是我们第一次访问该层级，需要在结果列表中添加一个初始值0
• 把结果列表中对应层级的计数加1
• 递归遍历当前节点的左子节点，层级加1
• 递归遍历当前节点的右子节点，层级加1
• 最后返回结果列表

代码示例（Python） #

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def level_order_count_dfs(root):
    result = []
    
    def dfs_helper(node, current_level):
        if not node:
            return
        # 首次访问该层级，初始化计数为0
        if current_level == len(result):
            result.append(0)
        # 当前层级计数加1
        result[current_level] += 1
        # 递归遍历左右子树
        dfs_helper(node.left, current_level + 1)
        dfs_helper(node.right, current_level + 1)
    
    dfs_helper(root, 0)
    return result

# 同样测试示例场景
root = TreeNode(1)
root.left = TreeNode(2)
root.right = TreeNode(3)
root.left.left = TreeNode(4)
print(level_order_count_dfs(root))  # 输出: [1, 2, 1]

两种方法的小对比 #

• BFS是迭代实现，不会有递归栈溢出的问题，适合处理非常深的二叉树
• DFS的代码更简洁，但如果树的深度超过Python默认的递归限制（默认是1000层），可能会报错，这时候就需要改成迭代版的DFS或者用BFS

内容的提问来源于stack exchange，提问作者YellowSnow15