这是悦乐书的第261次更新，第274篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第128题（顺位题号是559）。给定n-ary树，找到它的最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。例如，给定一个3-ary树：
image
我们应该返回它的最大深度，即3。
注意：
树的深度最多为1000。
节点总数最多为5000。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
这道题与求二叉树的最大深度是类似的，只不过二叉树是只有左右子节点，而这个n-ary树的子节点是一个数组，含有多个节点，所以我们只需要将左右子节点替换一下，变成for循环来处理，数组中包含的节点其实就是该问题的一个子问题，所以我们使用递归，调用方法自身，最后返回一个最大值即可。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
if (root.children == null) {
return 1;
}
int max = 0;
for (Node node : root.children) {
max = Math.max(max, maxDepth(node));
}
return max+1;
}
}
03 第二种解法
我们也可以使用迭代的方式来处理。我们使用队列先将根节点放入队列，然后开始循环处理，先将上一次放入队列的数据处理完，因此需要再使用一层循环，此层循环是处理每层的数据，因为其子节点是一个数组，还需要再使用一个循环来将新的节点放入队列，所以一共是三层循环，最后返回其深度即可。
/*
// Definition for a Node.
class Node {
public int val;
public List<Node> children;
public Node() {}
public Node(int _val,List<Node> _children) {
val = _val;
children = _children;
}
};
*/
class Solution {
public int maxDepth(Node root) {
if (root == null) {
return 0;
}
if (root.children == null) {
return 1;
}
Queue<Node> queue = new LinkedList<Node>();
queue.offer(root);
int depth = 0;
while (!queue.isEmpty()) {
int size = queue.size();
for (int i=0; i<size; i++) {
Node temp = queue.poll();
for (Node n : temp.children) {
queue.offer(n);
}
}
depth++;
}
return depth;
}
}
04 小结
算法专题目前已日更超过三个月，算法题文章128+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
