559. N叉树的最大深度

给定一个 N 叉树，找到其最大深度。
最大深度是指从根节点到最远叶子节点的最长路径上的节点总数。

例如

给定一个 3叉树 :

    1
   /|\
  3 2 4
 / \
5  6

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

说明:

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

思路1

使用递归，找到当前节点所有孩子节点中最深的一支，+1即为当前节点深度

性能分析

时间复杂度为O(N),空间复杂度最优为O(LogN)，最差为O(N)(全部为单支)

具体代码

int max(int a, int b){ // 辅助函数，用来返回较大值
    return a > b ? a : b;
}
int maxDepth(Node* root) {
    if(root == NULL){ //空节点过滤
        return 0;
    }
    int res = 0;
    for(int i = 0; i < root->children.size(); i++){ // 遍历每个子节点
        res = max(res, maxDepth(root->children[i])); // 选择最大子树深度
    }
    return 1 + res; // 最大子树深度 + 1 = 当前树深度
}

思路2

使用迭代，一层一层的遍历，每次把某一层的节点全部找出来，直到找不到下一层为止
存放的数据结构可以用队列，先进先出，后方插入前方弹出

性能分析

时间复杂度为O(N)，空间复杂度为O(N)

具体代码

queue<Node*> q;
int maxDepth(Node* root) {
    if(root == NULL) return 0; // 空节点筛除
    
    int res = 0;
    q.push(root);
    while(q.size()){ // 当该层还有节点
        for(int i = q.size(); i > 0; i--){ // 遍历该层所有节点
            Node* t = q.front(); // 获得队列头元素
            q.pop();             // 弹出队列头元素
            // 向队列尾插入队列头元素所有子节点
            for(int j = 0; j < t->children.size(); j++){
                q.push(t->children[j]);
            }
        }
        // 层数++
        res++;
    }
    
    return res;
}