LeetCode算法题-Maximum Depth of N-ary Tree(Java实现)

这是悦乐书的第261次更新,第274篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第128题(顺位题号是559)。给定n-ary树,找到它的最大深度。最大深度是从根节点到最远叶节点的最长路径上的节点数。例如,给定一个3-ary树:

LeetCode算法题-Maximum Depth of N-ary Tree(Java实现)

我们应该返回它的最大深度,即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+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:[洛谷P4886]快递员


下一篇:深入理解JVM—JVM内存模型