LeetCode算法题-Maximum Depth of N-ary Tree（Java实现）

佚名 5年前 (2019-02-27) 算法 555人围观抢沙发百度已收录

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

01 看题和准备

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

我们应该返回它的最大深度，即3。

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

注意：

树的深度最多为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;
    }
}