559. N 叉树的最大深度

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

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

N 叉树输入按层序遍历序列化表示，每组子节点由空值分隔（请参见示例）。

示例 1：

输入：root = [1,null,3,2,4,null,5,6]
输出：3

示例 2：

输入：root = [1,null,2,3,4,5,null,null,6,7,null,8,null,9,10,null,null,11,null,12,null,13,null,null,14]
输出：5

提示：

• 树的深度不会超过 1000 。
• 树的节点数目位于 [0, 104] 之间。

有返回值无信息参数的DFS，归并

递归计算每个子节点的深度，取最大值，返回+1

class Solution {
    public int maxDepth(Node root) {
        // 特殊条件：如果根节点为空，返回深度 0
        if (root == null) {
            return 0;
        }
        
        // 初始化最大子节点深度为 0
        int maxChildDepth = 0;
        
        // 获取当前节点的所有子节点
        List<Node> children = root.children;
        // 遍历所有子节点
        for (Node child : children) {
            // 递归计算每个子节点的深度
            int childDepth = maxDepth(child);
            // 更新最大子节点深度
            maxChildDepth = Math.max(maxChildDepth, childDepth);
        }
        
        // 当前节点的深度为最大子节点深度加 1
        return maxChildDepth + 1;
    }
}

• 时间复杂度：O(n)，其中 n 为 N 叉树节点的个数。每个节点在递归中只被遍历一次。
• 空间复杂度：O(height)，其中 height 表示 N 叉树的高度。递归函数需要栈空间，而栈空间取决于递归的深度，因此空间复杂度等价于 N 叉树的高度。

层序遍历

取出节点后要入队子节点，然后当前层的节点数减一，减到0后深度加一。

class Solution {
    public int maxDepth(Node root) {
        // 如果根节点为空，返回深度 0
        if (root == null) {
            return 0;
        }
        
        // 使用队列进行广度优先搜索
        Queue<Node> queue = new LinkedList<Node>();
        // 将根节点加入队列
        queue.offer(root);
        // 初始化深度为 0
        int ans = 0;
        
        // 当队列不为空时继续遍历
        while (!queue.isEmpty()) {
            // 获取当前层的节点数
            int size = queue.size();
            // 遍历当前层的所有节点
            while (size > 0) {
                // 从队列中取出一个节点
                Node node = queue.poll();
                // 获取该节点的所有子节点
                List<Node> children = node.children;
                // 将子节点加入队列
                for (Node child : children) {
                    queue.offer(child);
                }
                // 当前层节点数减 1
                size--;
            }
            
            // 当前层遍历完，深度加 1
            ans++;
        }
        
        // 返回最大深度
        return ans;
    }
}

• 时间复杂度：O(n)，其中 n 为 N 叉树的节点个数。与方法一同样的分析，每个节点只会被访问一次。
• 空间复杂度：此方法空间的消耗取决于队列存储的元素数量，其在最坏情况下会达到 O(n)。

回溯，无返回值无信息参数的DFS，全局变量。

class Solution {
    public int maxDepth(Node root) {
        traverse(root);
        return res;
    }

    // 记录递归遍历到的深度
    int depth = 0;
    // 记录最大的深度
    int res = 0;

    void traverse(Node root) {
        // 结束条件
        if (root == null) {
            return;
        }
        
        // 前序遍历位置
        depth++;
        res = Math.max(res, depth);
        for (Node child : root.children) {
            traverse(child);
        }
        // 后序遍历位置
        depth--;
    }
}

• 每个节点都会被访问一次，因此时间复杂度是O(n)，n是节点总数。
• 空间复杂度就是递归栈的深度，即N叉树的高度H。