网络异常，图片无法展示
|
题目描述
这是 LeetCode 上的 559. N 叉树的最大深度 ，难度为 简单。
Tag : 「DFS」、「BFS」
给定一个 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, 10^4][0,104] 之间。
DFS
根据题意，可以写出如下的 DFS 实现：从 rootroot 的所有子节点中的取最大深度，并在此基础上加一（统计 rootroot 节点）即是答案。
代码：
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(n)
- 空间复杂度：忽略递归带来的额外空间开销，复杂度为 O(1)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)
- 空间复杂度：O(n)O(n)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.559 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
