原文链接: https://leetcode-cn.com/problems/maximum-depth-of-n-ary-tree

英文原文

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

Nary-Tree input serialization is represented in their level order traversal, each group of children is separated by the null value (See examples).

 

Example 1:

Input: root = [1,null,3,2,4,null,5,6]
Output: 3

Example 2:

Input: root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
Output: 5

 

Constraints:

• The total number of nodes is in the range [0, 104].
• The depth of the n-ary tree is less than or equal to 1000.

中文题目

给定一个 N 叉树，找到其最大深度。

最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

 

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

 

提示：

• 树的深度不会超过 1000 。
• 树的节点数目位于 [0, 104] 之间。

通过代码

高赞题解

DFS

根据题意，可以写出如下的 DFS 实现：从 $root$ 的所有子节点中的取最大深度，并在此基础上加一（统计 $root$ 节点）即是答案。

代码：

[]
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int ans = 0;
        for (Node node : root.children) {
            ans = Math.max(ans, maxDepth(node));
        }
        return ans + 1;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：忽略递归带来的额外空间开销，复杂度为 $O(1)$

---

BFS

同理，可以使用 BFS 进行求解：其本质是对多叉树进行层序处理，当 BFS 过程结束，意味着达到最大层数（深度），所记录的最大层数（深度）即是答案。

代码：

[]
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int ans = 0;
        Deque<Node> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            int size = d.size();
            while (size-- > 0) {
                Node t = d.pollFirst();
                for (Node node : t.children) {
                    d.addLast(node);
                }
            }
            ans++;
        }
        return ans;
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$

---

其他「BFS/DFS」相关内容

1. DFS

题目	题解	难度	推荐指数
17. 电话号码的字母组合	LeetCode 题解链接	中等	🤩🤩🤩🤩
22. 括号生成	LeetCode 题解链接	中等	🤩🤩🤩🤩
37. 解数独	LeetCode 题解链接	困难	🤩🤩🤩🤩
39. 组合总和	LeetCode 题解链接	中等	🤩🤩🤩🤩
40. 组合总和 II	LeetCode 题解链接	中等	🤩🤩🤩🤩
211. 添加与搜索单词 - 数据结构设计	LeetCode 题解链接	中等	🤩🤩🤩🤩🤩
282. 给表达式添加运算符	LeetCode 题解链接	困难	🤩🤩🤩🤩
301. 删除无效的括号	LeetCode 题解链接	困难	🤩🤩🤩🤩
341. 扁平化嵌套列表迭代器	LeetCode 题解链接	中等	🤩🤩🤩
397. 整数替换	LeetCode 题解链接	中等	🤩🤩🤩🤩
403. 青蛙过河	LeetCode 题解链接	困难	🤩🤩🤩🤩
437. 路径总和 III	LeetCode 题解链接	中等	🤩🤩🤩🤩
488. 祖玛游戏	LeetCode 题解链接	困难	🤩🤩🤩🤩
494. 目标和	LeetCode 题解链接	中等	🤩🤩🤩🤩
563. 二叉树的坡度	LeetCode 题解链接	简单	🤩🤩🤩🤩
638. 大礼包	LeetCode 题解链接	中等	🤩🤩🤩🤩
677. 键值映射	LeetCode 题解链接	中等	🤩🤩🤩🤩
690. 员工的重要性	LeetCode 题解链接	简单	🤩🤩🤩
778. 水位上升的泳池中游泳	LeetCode 题解链接	困难	🤩🤩🤩
783. 二叉搜索树节点最小距离	LeetCode 题解链接	简单	🤩🤩🤩
869. 重新排序得到 2 的幂	LeetCode 题解链接	中等	🤩🤩🤩🤩
872. 叶子相似的树	LeetCode 题解链接	简单	🤩🤩🤩
938. 二叉搜索树的范围和	LeetCode 题解链接	简单	🤩🤩🤩
987. 二叉树的垂序遍历	LeetCode 题解链接	困难	🤩🤩🤩🤩🤩
993. 二叉树的堂兄弟节点	LeetCode 题解链接	简单	🤩🤩
1239. 串联字符串的最大长度	LeetCode 题解链接	中等	🤩🤩🤩
1723. 完成所有工作的最短时间	LeetCode 题解链接	困难	🤩🤩🤩
1766. 互质树	LeetCode 题解链接	困难	🤩🤩🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

2. BFS

题目	题解	难度	推荐指数
90. 子集 II	LeetCode 题解链接	中等	🤩🤩🤩🤩
297. 二叉树的序列化与反序列化	LeetCode 题解链接	困难	🤩🤩🤩🤩
397. 整数替换	LeetCode 题解链接	中等	🤩🤩🤩🤩
403. 青蛙过河	LeetCode 题解链接	困难	🤩🤩🤩🤩
690. 员工的重要性	LeetCode 题解链接	简单	🤩🤩🤩
778. 水位上升的泳池中游泳	LeetCode 题解链接	困难	🤩🤩🤩
783. 二叉搜索树节点最小距离	LeetCode 题解链接	简单	🤩🤩🤩
938. 二叉搜索树的范围和	LeetCode 题解链接	简单	🤩🤩🤩
993. 二叉树的堂兄弟节点	LeetCode 题解链接	简单	🤩🤩

注：以上目录整理来自 wiki，任何形式的转载引用请保留出处。

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
89392	120865	74.0%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言

相似题目

题目	难度
二叉树的最大深度	简单