IT 面试题库

二叉树的层序遍历(BFS):① 要求按层输出(每层一个子数组)② 进阶之字形(Z 字)打印,给出实现与复杂度。

高级编程题算法工程师Java后端工程师二叉树层序遍历BFS之字形Z字打印

题目

考察点:BFS 按层分桶、之字形(奇偶层反转)技巧。这是遍历追问链的收尾,综合层序与数组操作。

参考答案

内容深度:适中 · 含示例/代码 · 来源:外部链接 · 未复核 · 70 天前更新 · 技术内容可能随版本变化,建议结合官方文档理解

要点:

参考实现(按层分桶 + 之字):

function zigzagLevelOrder(root) {
  if (!root) return [];
  const res = [], q = [root];
  let level = 0;
  while (q.length) {
    const len = q.length, layer = [];
    for (let i = 0; i < len; i++) {
      const n = q.shift();
      layer.push(n.val);
      if (n.left) q.push(n.left);
      if (n.right) q.push(n.right);
    }
    if (level % 2 === 1) layer.reverse();  // 奇数层反转成 Z 字
    res.push(layer);
    level++;
  }
  return res;
}
练这道题

同分类 · 高频题

题目与答案就在本页;收藏、批注和错题重练在应用内

这道题看完了?连刷同类题,趁热打铁效果最好 进入刷题