二叉树 + BFS

这一组题的共同基础是：把树或网格看成由节点和边组成的结构，再选择合适的遍历顺序。

先判断用 BFS 还是 DFS

题目核心方法判断依据
102. 二叉树的层序遍历BFS答案按层组织
103. 锯齿形层序遍历BFS仍按层遍历，只改变每层的写入方向
199. 二叉树的右视图BFS取每层最后一个节点
101. 对称二叉树DFS / BFS成对比较镜像位置
236. 最近公共祖先后序 DFS需要汇总左右子树的查找结果
572. 另一棵树的子树DFS枚举根节点，并递归比较两棵树

BFS 层序遍历模板

const queue = [root];
let head = 0;

while (head < queue.length) {
  const levelSize = queue.length - head;

  for (let i = 0; i < levelSize; i++) {
    const node = queue[head++];

    if (node.left) queue.push(node.left);
    if (node.right) queue.push(node.right);
  }
}

levelSize 必须在处理本层之前固定下来，否则新加入的下一层节点也会被当成本层处理。使用 head 指针代替 queue.shift()，可以避免数组反复移动元素。

二叉树 DFS 三种遍历

二叉树 DFS 的区别主要在于“什么时候访问当前节点”。

遍历方式访问顺序适合场景
前序遍历根 → 左 → 右先处理当前节点，再继续处理子树，例如复制树、序列化树
中序遍历左 → 根 → 右二叉搜索树中可以得到有序结果
后序遍历左 → 右 → 根先拿到左右子树结果，再处理当前节点，例如树高、直径、最近公共祖先

前序遍历

function preorder(root) {
  if (!root) return;

  // 先访问当前节点
  visit(root);
  preorder(root.left);
  preorder(root.right);
}

前序遍历的特点是“先看自己，再看孩子”。如果题目要求从根节点开始构造、记录或传递状态，通常可以优先考虑前序。

中序遍历

function inorder(root) {
  if (!root) return;

  inorder(root.left);
  // 中间访问当前节点
  visit(root);
  inorder(root.right);
}

中序遍历在普通二叉树中只是固定的访问顺序；在二叉搜索树中更重要，因为访问结果天然按从小到大排列。

后序遍历

function postorder(root) {
  if (!root) return;

  postorder(root.left);
  postorder(root.right);
  // 最后访问当前节点
  visit(root);
}

后序遍历的特点是“先处理左右子树，再处理当前节点”。如果当前节点的答案依赖左右子树的返回值，通常就是后序 DFS，例如判断平衡二叉树、计算二叉树直径、寻找最近公共祖先。

网格 BFS 模板

const directions = [
  [1, 0],
  [-1, 0],
  [0, 1],
  [0, -1],
];

const queue = [[startRow, startColumn]];
let head = 0;

while (head < queue.length) {
  const [row, column] = queue[head++];

  for (const [rowOffset, columnOffset] of directions) {
    const nextRow = row + rowOffset;
    const nextColumn = column + columnOffset;
    // 判断边界、是否可访问，并在入队时标记
  }
}

网格搜索要在节点入队时标记已访问。如果出队时才标记，同一格可能被多个相邻格重复加入队列。