二叉树的最大深度

🟢 Easy · 🏷️ 树、递归、DFS · LeetCode#104

📖 题目

求一棵二叉树的最大深度——根节点到最远叶子节点的最长路径上的节点数。

    3        深度 = 3
   / \
  9  20
    /  \
   15   7

💡 思路

树的递归，思路是把大问题"甩给未来的自己"：不用去想整棵树怎么算，只要相信"子树的深度递归调用就能算出来"，当前节点的深度就是 1 + max(左子树深度, 右子树深度)。递归出口是空节点，深度为 0。

以样例展开：

maxDepth(9)  = 1 + max(0, 0) = 1
maxDepth(20) = 1 + max(maxDepth(15), maxDepth(7)) = 1 + max(1, 1) = 2
maxDepth(3)  = 1 + max(maxDepth(9), maxDepth(20)) = 1 + max(1, 2) = 3

绝大多数树的递归题都是这个骨架：判断空节点 → 递归处理左右子树 → 用子树的结果算出当前节点的答案。

💻 代码

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        return 1 + max(self.maxDepth(root.left), self.maxDepth(root.right))

时间复杂度 O(n)，每个节点访问一次；空间复杂度 O(h)，h 是树高，取决于递归栈的深度。