考察点:递归(自底向上/后序)与 BFS(按层计数)两种解法的转换,复杂度分析。顺接遍历之后进入「深度」维度。
要点:
maxDepth(root) = root ? 1 + max(maxDepth(left), maxDepth(right)) : 0,本质是后序遍历——先求左右子树深度再 +1。depth++,直到队列空;层与层之间用「先记录当前队列长度 len,只处理这 len 个节点」来隔离。参考实现:
// 递归
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;
}题目与答案就在本页;收藏、批注和错题重练在应用内