N 叉树的最大深度

问题描述

来源：LeetCode第559题

难度：简单

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

问题分析

N 叉树就是每个节点最多有 N 个子节点，这题让求 N 叉树的最大深度，我们还是可以参照二叉树的解题方式使用 BFS ，就一层一层的遍历，计算总共有多少层即可，代码比较简单，我们就不在写了。我们来看下这题的 DFS 解决思路，这里来参考下二叉树的 DFS 解题思路，二叉树我们是把所有子节点的结果都计算出来，最后在合并，这题也一样，虽然我们不知道具体有多少个子节点，没法一个个列出来，但我们可以使用一个 for 循环来遍历，代码如下：

public int maxDepth(Node root) {
    if (root == null)
        return 0;
    // 当前节点子节点的个数
    int size = root.children.size();
    int max = 0;
    // 递归计算所有子节点的深度，保留最大值
    for (int i = 0; i < size; i++)
        max = Math.max(max, maxDepth(root.children.get(i)));
    // 当前树的最大深度就是子节点的最大深度加上1
    return max + 1;
}