二叉树的最大深度

问题拆解

题目要的是根节点到最远叶子的路径上有多少个节点。第一反应可能是去枚举所有从根到叶子的路径，比较谁最长，但这样既要记录路径又要回溯，写起来很啰嗦。

真正的关键是换一个视角：一棵树的最大深度，等于它两棵子树中较深那棵的深度，再加上根节点自己这一层。

深度这个量对整棵树的定义，和对任意子树的定义完全一样。这正是递归能生效的信号。

后序递归

先算出左右子树的深度，再合并成当前树的答案——这是典型的后序处理顺序：

def maxDepth(root):
    if not root:
        return 0
    return 1 + max(maxDepth(root.left), maxDepth(root.right))

空树的深度是 0，这既是递归的终点，也让叶子节点自然得到 1 + max(0, 0) = 1。整个函数几乎就是把「深度 = 较深子树 + 1」这句话原样抄成了代码。

如果担心极端瘦长的树把递归栈压爆，可以改用层序遍历，一层一层往下数，遍历了几层深度就是几。但对本题的数据规模，递归写法足够清晰。

复杂度

指标	复杂度	原因
时间	O(n)	每个节点恰好被访问一次
空间	O(h)	递归栈深度等于树高，最坏退化成 O(n)

可以迁移的模式

• 当一个量「对整体的定义」和「对局部的定义」一致时，优先考虑递归；
• 后序处理适合「答案要靠孩子先算好再汇总」的场景；
• 空节点返回一个恰当的边界值（这里是 0），能让叶子的计算无需特判。

先想清楚返回值代表什么，再写递归体，往往比先写代码再补语义顺得多。