技术总监强制周三不加班，反卷之余搞懂N叉树最大深度（递归&BFS）

刚刷到一个大厂员工的爆料，看得人哭笑不得，又忍不住有点羡慕。

他们技术总监，40岁的行业大牛，一不卷工时，二不演苦劳，直接立了条规矩：每周三雷打不动到点就走，谁也不许在工位上演忙碌。

有些公司最爱搞那种表演型奋斗——白天开会扯皮，晚上点灯熬油补活儿，最后人累垮了，项目也没见多神。这个总监敢把“下班去生活”正儿八经当成规矩，我觉得挺狠的。职场里最难的不是喊口号，是领导自己先别演。下属一看老板都拎包撤了，才敢真跟着收工啊。

面试题：N叉树的最大深度

别一上来就把题目想复杂了

如果 root = null，深度就是 0。这个判断不写，后面代码再花哨都白搭。

N叉树这题看着比二叉树吓人，其实麻烦点就一个：每个节点的孩子不是 left、right，而是一个 children 列表。按人脑的逻辑走一遍，一个节点的最大深度 = 所有子节点的最大深度里取最大值，再把自己这一层 +1 就行。叶子节点没有孩子，深度就是 1。

递归代码可以这么写：

import java.util.List;

class Node {
    int val;
    List<Node> children;

    Node(int val, List<Node> children) {
        this.val = val;
        this.children = children;
    }
}

class Solution {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        int childMaxDepth = 0;

        if (root.children != null) {
            for (Node child : root.children) {
                int depth = maxDepth(child);
                if (depth > childMaxDepth) {
                    childMaxDepth = depth;
                }
            }
        }

        return childMaxDepth + 1;
    }
}

这段代码里最关键的地方不是递归本身，而是这个变量：

int childMaxDepth = 0;

它不是记录当前节点自己的深度，而是用来存放“子树里最深的那条路的长度”。把所有的孩子都扫一遍，谁最深就用谁的，最后 +1 把当前节点这一层加进去。例如这棵树：

        1
     /  |  \
    2   3   4
       / \
      5   6

节点 5 没有孩子，返回 1。节点 6 同样返回 1。节点 3 看到两个孩子最大深度是 1，于是返回 2。节点 1 再比较 2、3、4 三个孩子，发现节点 3 这条路最深，最后返回 3。递归路线就是 1 -> 3 -> 5 或 1 -> 3 -> 6，一共 3 层。

这题有个容易写别扭的地方：有人非要在递归里传一个 level 参数，一边往下走一边更新全局最大值。不是不能写，只是真没这个必要。让函数自己返回结果，比到处改外部变量更容易看、更好调。

如果树特别深，递归可能会压栈。刷题时一般还好，但真在工程里碰上那种层级目录、组织架构树、类目树，我更愿意写 BFS。层数一层一层数出来，排查结构问题也更直观：

import java.util.ArrayDeque;
import java.util.Queue;

class SolutionBfs {
    public int maxDepth(Node root) {
        if (root == null) {
            return 0;
        }

        Queue<Node> queue = new ArrayDeque<>();
        queue.offer(root);

        int depth = 0;

        while (!queue.isEmpty()) {
            int levelSize = queue.size();
            depth++;

            for (int i = 0; i < levelSize; i++) {
                Node node = queue.poll();

                if (node.children == null) {
                    continue;
                }

                for (Node child : node.children) {
                    if (child != null) {
                        queue.offer(child);
                    }
                }
            }
        }

        return depth;
    }
}

DFS 写起来短，适合面试和快速刷题；BFS 多几行，但逻辑更符合按层思考的习惯。

时间复杂度没什么花活，每个节点都访问一次，所以是 O(n)。空间复杂度看树的形状：递归 DFS 主要吃调用栈，BFS 主要吃队列。

最后一句话：别背模板，记住一条就够了——当前节点的最大深度，等于最深孩子的深度加一。