BFS：层序遍历（树与图）

BFS：层序遍历（树与图）

一、面试常考点

1. 层序遍历模板

每轮先固定当前层的队尾边界，保证同层一起处理；新加入的孩子留到下一轮访问。（深入阅读：1. 树层序）

2. 变体

自底向上层序只调整层的顺序，同一层仍从左向右。其他常见变体还有锯齿层序、右视图、每层最大值。（深入阅读：自底向上层序遍历）

二、细节介绍

1. 树层序

输入应是有限、无环且没有共享子节点的二叉树，节点字段为 val、left 和 right；空树返回 []。访问父节点时先加入左孩子，再加入右孩子，才能保留同一层从左向右的顺序。

使用数组和 head 索引模拟队列，不必通过 shift() 搬移已有元素。每轮开始固定 levelEnd = queue.length，当前层就是 [head, levelEnd)；即使遍历中继续 push 孩子，也不改变这个边界。下一轮再把新队尾作为边界，否则不同深度的节点会被混入同一层。

2. 图层序

必须加 visited 防回路。

三、示例代码

1. 自顶向下层序遍历

function levelOrder(root) {
  if (root == null) return []
  const res = []
  const queue = [root]
  let head = 0

  while (head < queue.length) {
    const levelEnd = queue.length
    const level = []
    while (head < levelEnd) {
      const node = queue[head++]
      level.push(node.val)
      if (node.left != null) queue.push(node.left)
      if (node.right != null) queue.push(node.right)
    }
    res.push(level)
  }

  return res
}

每个节点只入队和访问一次，时间复杂度为 O(n)。结果保存全部节点值，占 O(n) 输出空间；上面的队列通过索引消费，仍保留已访问节点，因此额外空间也是 O(n)，不能只按当前层宽度计算。单链状的树虽然每层只有一个节点，这个实现的队列仍会累计 n 个引用。

2. 自底向上层序遍历

先按正常 BFS 得到各层，再反转最外层数组即可。反转的是层的顺序，不是每层内部的节点顺序；对每一层调用 reverse() 会错误地变成从右向左。

function levelOrderBottom(root) {
  return levelOrder(root).reverse()
}

例如 [3,9,20,null,null,15,7] 表示的二叉树，自顶向下结果是 [[3], [9,20], [15,7]]，自底向上则是 [[15,7], [9,20], [3]]。levelOrder 每次返回新数组，所以这里的 reverse() 不会修改输入树或其他调用的结果。

若有 L 层，外层反转只需 O(L) 时间，且 L <= n，总时间仍为 O(n)。反转本身原地交换层数组的引用，不复制每层内容；完整实现仍需 O(n) 的结果空间和 O(n) 的历史队列空间。

不要为每层反复调用 unshift(level)：它需要把之前的层向后搬移，单链树有 n 层时可能累计 O(n²) 成本。自底向上也不等于后序遍历，后序按子树组织，并不保证相同深度的节点连续输出。

四、常用应用场景

1. 组织架构分层展示

按层渲染树结构。

2. 传播模拟

消息逐层扩散过程。

五、边界与验证

输入	自顶向下	自底向上
空树	[]	[]
单节点 3	[[3]]	[[3]]
单节点 0	[[0]]	[[0]]
根 1 的左右孩子均为 2	[[1], [2, 2]]	[[2, 2], [1]]
单链 1 -> 2 -> 3	[[1], [2], [3]]	[[3], [2], [1]]
不满树 [3,9,20,null,null,15,7]	[[3], [9,20], [15,7]]	[[15,7], [9,20], [3]]

缺失孩子不入队，也不输出 null 占位。对于不规则树，仍按深度划分层，不能把“自底向上”理解为按叶子节点倒序访问。若输入可能成环或共享子节点，需要先明确它是树还是图，并使用访问标记或输入校验。