题目描述
思路解析
一句话答案：LeetCode 559 N 叉树的最大深度：从根到最远叶子经过几个节点。递归求解，每个节点的深度 = 1 加上所有孩子里最深的那个子树深度，没有孩子就记 1，时间 O(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。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记牢「先算孩子、取最大、加一层」，下面每一帧都在套它。
准备 · 从根出发：先看整棵树。我们要算根 50 的子树深度。办法是从根往下递归:先把每个孩子的子树深度都算清楚，再取最大、加上自己这一层。下面跟着紫色的「当前节点」一路下探。
下行 · 进入 50：走到节点 50（紫色）。它的孩子列表有 2 个:30、80。想知道 50 的深度，得先把这几个孩子的子树深度逐个算出来。
下探 · 50 的孩子：按后序的规矩，先把第一个孩子 30 的子树彻底算完，再回头看 50 剩下的孩子。我们顺着这条边往下走。
下行 · 进入 30：走到节点 30（紫色）。它的孩子列表有 2 个:10、20。想知道 30 的深度，得先把这几个孩子的子树深度逐个算出来。
下探 · 30 的孩子：按后序的规矩，先把第一个孩子 10 的子树彻底算完，再回头看 30 剩下的孩子。我们顺着这条边往下走。
下行 · 叶子 10：走到节点 10（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
结算 · 10 = 1：叶子 10 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 10 标绿，表示它的深度已经定下来了。
返回 · 回到 30：孩子 10 那一支已经算完(深度 1)，回到 30。它还有孩子没算，接着深入下一个 20。
下行 · 叶子 20：走到节点 20（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
结算 · 20 = 1：叶子 20 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 20 标绿，表示它的深度已经定下来了。
汇总 · 30 的孩子：30 的孩子都算完了，子树深度分别是 1、1。我们要的是最深的那个，取最大值得到 1。正在判定 30，先别急着定色。
结算 · 30 = 2：最深的孩子子树是 1，加上 30 自己这一层，30 的子树深度 = 1 + 1 = 2。节点 30 标绿，深度敲定。
返回 · 回到 50：孩子 30 那一支已经算完(深度 2)，回到 50。它还有孩子没算，接着深入下一个 80。
下行 · 进入 80：走到节点 80（紫色）。它的孩子列表有 1 个:60。想知道 80 的深度，得先把这几个孩子的子树深度逐个算出来。
下探 · 80 的孩子：按后序的规矩，先把第一个孩子 60 的子树彻底算完，再回头看 80 剩下的孩子。我们顺着这条边往下走。
下行 · 叶子 60：走到节点 60（紫色）。它的孩子列表是空的，是个叶子，不用再往下了。
结算 · 60 = 1：叶子 60 没有孩子，最深孩子算 0，加上自己这一层，子树深度就是 1。节点 60 标绿，表示它的深度已经定下来了。
汇总 · 80 的孩子：80 的孩子都算完了，子树深度分别是 1。我们要的是最深的那个，取最大值得到 1。正在判定 80，先别急着定色。
结算 · 80 = 2：最深的孩子子树是 1，加上 80 自己这一层，80 的子树深度 = 1 + 1 = 2。节点 80 标绿，深度敲定。
汇总 · 50 的孩子：50 的孩子都算完了，子树深度分别是 2、2。我们要的是最深的那个，取最大值得到 2。正在判定 50，先别急着定色。
结算 · 50 = 3：最深的孩子子树是 2，加上 50 自己这一层，50 的子树深度 = 1 + 2 = 3。节点 50 标绿，深度敲定。
完成：所有节点都结算完了。根 50 的两个孩子 30 和 80 子树深度都是 2，取最大 2 再加 1，根的子树深度就是 3。这正是从根到最远叶子那条路上的节点数，答案 = 3。
边界先想清:空树 0、单节点 1；孩子很多但都是叶子时深度还是 2，宽度不影响深度。
面试常被追问和 lc104 的关系、以及迭代写法(BFS 数层数)。
参考代码
from typing import Listclass 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])复杂度
- 时间：O(n)，每个节点恰好被访问一次，做的都是常数工作(取最大、加一)，n 是节点总数
- 空间：O(h)，递归栈深度等于树高 h；最坏退化成一条链时 h 可达 n
易错点
面试追问把动画讲成自己的话
追问这题和二叉树最大深度(LeetCode 104)有什么区别?
追问能不能不用递归，改成迭代?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
二叉树的坡度
LeetCode 563 · 简单 · 沿着 树套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题