IT 面试题库

求二叉树的最大深度,请用递归和层序遍历(BFS)两种思路实现,并说明复杂度。

中级编程题算法工程师Java后端工程师二叉树最大深度递归BFS层序

题目

考察点:递归(自底向上/后序)与 BFS(按层计数)两种解法的转换,复杂度分析。顺接遍历之后进入「深度」维度。

参考答案

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

要点:

参考实现:

// 递归
const maxDepth = (root) => root ? 1 + Math.max(maxDepth(root.left), maxDepth(root.right)) : 0;
// 层序
function maxDepthBFS(root) {
  if (!root) return 0;
  let depth = 0, q = [root];
  while (q.length) {
    depth++;
    const next = [];
    for (const n of q) { if (n.left) next.push(n.left); if (n.right) next.push(n.right); }
    q = next;
  }
  return depth;
}
练这道题

同分类 · 高频题

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

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