Easy

Given a n-ary tree, find its maximum depth.

The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.

For example, given a 3-ary tree:

 

 

We should return its max depth, which is 3.

 

Note:

1. The depth of the tree is at most 1000.
2. The total number of nodes is at most 5000.

题目大意：求出n叉树的深度。

 

方法：遍历n叉树，找到最大高度。

方法一：递归遍历

代码如下：

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root)return 0;
        int res=1;
        if(!root->children.empty()){
            int temp=0;
            for(auto child:root->children){
                temp=max(temp,maxDepth(child));
            }
            res+=temp;
        }
        return res;
    }
};

 

方法二：迭代法，使用队列queue，每次都将一整层的节点遍历一次，将他们的子节点放入队列中，同时层数+1.

代码如下：

class Solution {
public:
    int maxDepth(Node* root) {
        if(!root)return 0;
        int res=0;
        queue<Node*> q{{root}};
        while(!q.empty()){
            for(int i=q.size();i>0;--i){
                Node* temp=q.front();
                q.pop();
                if(!temp->children.empty()){
                    for(auto child:temp->children){
                        q.push(child);
                    }
                }
            }
            ++res;
        }
        return res;
    }
};