LeetCode559. N叉树的最大深度-蒲公英云

LeetCode559. N叉树的最大深度

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

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

例如，给定一个 3叉树 :

我们应返回其最大深度，3。

说明:

树的深度不会超过 1000。
树的节点总不会超过 5000。

思路：广度优先遍历树，计算树的层数，最大层数就是树最大深度。

/*
// 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(null==root){
            return 0;
        }
        ArrayDeque<Node> queue=new ArrayDeque<Node>();
        queue.add(root);
        int count=0;
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                Node node=queue.removeFirst();
                for(Node n:node.children){
                    queue.add(n);
                }
            }
            count++;
        }
        return count;
    }
}

解法二：

/*
// 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(null==root){
            return 0;
        }
        int res=1;
        for(Node n:root.children){
            res=Math.max(maxDepth2(n)+1,res);
        }
        return res;
    }
}