N 叉树的最大深度 图解题解

从根到最远叶子，一共要数几个节点

给一棵 N 叉树的根 root，要返回它的最大深度，也就是从根节点到最远那个叶子、一路上经过的节点总数。N 叉树，也就是每个节点可以挂任意多个孩子——0 个、1 个、2 个甚至更多，这些孩子都放在一个列表里。题面给的例子是 root = [50,[30,[10,20],80,[60]]]：根 50 底下挂着 30 和 80，30 又挂着 10、20，80 挂着一个 60。最远的一条路是 50 到 10（20、60 也一样长），一共 3 个节点，答案就是 3。

为什么不能只顺着一个孩子往下数

N 叉树的麻烦在于孩子个数不固定。要是照搬二叉树那种「往左往右各探一次」的写法，只挑列表里第一个孩子递归下去，就可能漏掉真正最深的那一支：万一最长的路径藏在第三个、第五个孩子那边，只看第一个孩子算出来的深度就偏小了。所以一个节点的所有孩子都得逐个算过，一个都不能落下。

深度 = 1 加上最深的那个孩子

换个数法就顺了：一个节点的深度，等于它孩子里最深的那棵子树深度，再加上自己这一层。叶子没有孩子，最深孩子按 0 算，加上自己就是 1；往上每一层，都在下面最深子树的基础上加一。这样一个大问题就拆成了同样形状的小问题——求某个节点的深度，先求出它每个孩子的深度，取其中最大值，再加 1，就是当前节点的深度。

递归函数在每个节点做什么、返回什么

落到递归函数上，逻辑很短。传进来一个节点：如果它是空的，直接返回 0；否则遍历它 children 列表里的每个孩子，对每个孩子递归求出子树深度，把这些深度取最大值，最后加 1 返回。参考代码里那句 1 加上孩子深度列表的最大值，就是这个意思；孩子列表为空时用 0 兜底，保证叶子返回 1 而不是出错。每一层返回给上一层的，永远是「我这棵子树有多深」，一层层加回去，根拿到的就是整棵树的最大深度。

拿题面这棵树，从叶子逐层加回根

从最底下的叶子往回结算。叶子 10 没有孩子，深度 1；叶子 20 也是深度 1。回到它们的父亲 30，两个孩子深度都是 1，取最大 1 再加自己一层，30 的深度 = 1 + 1 = 2。另一边，叶子 60 深度 1，它的父亲 80 只有这一个孩子，取最大 1 加一层，80 的深度也是 2。最后回到根 50，它的两个孩子 30 和 80 深度都是 2，取最大 2 再加根自己这一层，50 的深度 = 1 + 2 = 3。这条最深的路正好经过 3 个节点，和答案 3 对得上。

复杂度，以及空树和瘦长链两个边界

每个节点只被访问一次，做的都是常数工作——取最大、加一，所以时间是 O(n)，n 是节点总数。额外开销来自递归的调用栈，最深压到树高那么多层，记作 O(h)；当树退化成一条链、每个节点都只有一个孩子时，h 会等于 n。两个边界要盯紧：空树必须返回 0 而不是 1，否则整棵树凭空多算一层；还有别把「取最大」写成「把所有孩子深度加起来」，深度看的是最长的一条路径，不是把所有分支加总。孩子再多但都是叶子，深度也还是 2。

Python

from typing import List
class Node:
    def __init__(self, val=None, children=None):
        self.val = val
        self.children = children if children is not None else []
class Solution:
    def maxDepth(self, root: 'Node') -> int:
        if not root:
            return 0
        return 1 + max([self.maxDepth(c) for c in root.children] or [0])

C++

#include <algorithm>
#include <functional>
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class Node {
public:
    int val;
    vector<Node*> children;
    Node() {}
    Node(int _val) { val = _val; }
    Node(int _val, vector<Node*> _children) { val = _val; children = _children; }
};
class Solution {
public:
    int maxDepth(Node* root) {
        if (!root) return 0;
        int best = 0;
        for (Node* child : root->children) best = max(best, maxDepth(child));
        return best + 1;
    }

};

Java

import java.util.*;
class Node {
    public int val;
    public List<Node> children;
    public Node() { children = new ArrayList<>(); }
    public Node(int _val) { val = _val; children = new ArrayList<>(); }
    public Node(int _val, List<Node> _children) { val = _val; children = _children; }
}
class Solution {
    public int maxDepth(Node root) {
        if (root == null) return 0;
        int best = 0;
        for (Node child : root.children) best = Math.max(best, maxDepth(child));
        return best + 1;
    }

}