BFS：层序遍历（树与图）

一、面试常考点

1. 层序遍历模板

每轮先记录当前队列长度，保证同层一起处理。

2. 变体

锯齿层序、右视图、每层最大值。

二、细节介绍

1. 树层序

天然无环，但仍注意空节点判断。

2. 图层序

必须加 visited 防回路。

三、示例代码

function levelOrder(root) {
  if (!root) return []
  const res = []
  const queue = [root]

  while (queue.length) {
    const size = queue.length
    const level = []
    for (let i = 0; i < size; i++) {
      const node = queue.shift()
      level.push(node.val)
      if (node.left) queue.push(node.left)
      if (node.right) queue.push(node.right)
    }
    res.push(level)
  }

  return res
}

四、常用应用场景

1. 组织架构分层展示

按层渲染树结构。

2. 传播模拟

消息逐层扩散过程。