LeetCode 559. N 叉树的最大深度
题目描述
题意分析
给定一棵 N 叉树，返回从根节点到最远叶子节点的路径上包含多少个节点，这个数量就是最大深度。它按节点数计算，不是边数；空树深度为零，只有根节点的树深度为一。
一个节点可以有多个孩子，需要比较所有孩子方向的深度。根到叶子的路径只会选择其中一个孩子继续向下，不会同时经过多个兄弟分支，因此不能把各子树的深度相加。
解法：递归深度优先搜索
核心思路
[!blue]
定义
maxDepth(root)返回以root为根的子树的最大深度，并且返回值包含当前根这一层。若根为空，返回零，作为递归的结束条件。对非空节点，一条向下路径先经过当前节点，再进入某个孩子的子树。要让整条路径最长，就选择深度最大的那个孩子。因此先递归求出每个孩子的深度，用
childMax保存最大值，最后返回childMax + 1。这既是可达到的深度，也是上界：选择最深孩子中的最长路径，确实可以形成这么长的根到叶子路径；其他孩子的深度都不超过它，不可能得到更长的路径。每个子树都按相同规则返回，递归结束后根节点得到整棵树的答案。
childMax初始为零。叶子没有孩子，循环不会改变这个初值，最终自然返回一，因此不需要额外写一个叶子节点分支。题面序列化中的空标记只是用来分隔孩子列表，并不是额外的一层节点。
解题步骤
- 当前根为空时返回零。
- 初始化
childMax = 0。- 遍历当前节点的所有孩子，递归求各自的最大深度，保留最大返回值。
- 返回
childMax + 1，加上当前节点所在的一层。
代码实现
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
// 返回节点层数，无孩子时零加一得到叶深度
int childMax = 0;
for (Node child : root.children) {
childMax = Math.max(childMax, maxDepth(child));
}
return childMax + 1;
}
}
func maxDepth(root *Node) int {
if root == nil {
return 0
}
// 返回节点层数，无孩子时零加一得到叶深度
childMax := 0
for _, child := range root.Children {
depth := maxDepth(child)
if depth > childMax {
childMax = depth
}
}
return childMax + 1
}
复杂度分析
- 时间复杂度：$O(n)$，其中
n为节点数。每个节点访问一次，所有孩子列表中合计只有树的n - 1条父子边。- 空间复杂度：$O(h)$，其中
h为树高。虽然一个节点可能有多个孩子，但它们依次递归，同一时刻调用栈只保留一条从根向下的路径，最坏为 $O(n)$。
关键点总结
[!green]
- 返回值表示当前子树的节点深度，与当前节点在整棵树中的层号不同。
- 兄弟子树之间取最大值，当前节点这一层只在最终加一次。
- 零初值和最后加一统一处理叶子，空根则单独返回零。
易错点总结
[!yellow]
- 把各孩子深度相加，会把不同分支合成一条不存在的路径。
- 忘记最后加一，会漏掉当前节点，叶子也会错误返回零。
- 把加一放在遍历孩子的累计操作中，会把孩子数量误算成额外层数；应取完最大值再统一加一。
- 把空树深度设为一，会让空输入本身得到错误结果。
- 只处理第一个孩子或只写两个孩子，无法覆盖 N 叉树全部可能的最深分支。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 104. 二叉树的最大深度 | 简单 | 最大深度递推相同，只需把固定两个孩子扩展成children列表取最大。 |
| 429. N 叉树的层序遍历 | 中等 | N叉树层序遍历的层数同样给出最大深度，可对比BFS与DFS的空间来源。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！