二叉树的最大深度

给定一棵二叉树 root，返回它的最大深度。最大深度是从根节点到最远叶子节点路径上的节点数。

这里数的是节点，不是边。单节点树的最大深度是 1，空树的最大深度是 0。

• • 节点数量范围通常允许空树。
• • 树可能平衡，也可能退化成一条链。
• • 答案只关心最深的一条根到叶路径。

输入：root = [3,9,20,null,null,15,7]
输出：3
解释：最长路径可以是 3 → 20 → 15，共经过 3 个节点。

把 maxDepth(node) 定义为：以 node 为根的这棵子树，最深有多少层。这个定义决定了递归应该返回什么。

如果 node 是 nil，它下面没有任何节点，所以返回 0。如果 node 非空，答案至少包含自己这一层。

直观做法是 DFS 枚举每一条根到叶路径，携带当前 depth，到叶子时更新全局最大值。这种写法能通过，也能做到 O(n)。

它的问题不是复杂度错误，而是需要额外的全局状态，教学上也容易把“访问深度”和“函数返回含义”混在一起。

dfs(node, depth)
  到达叶子：answer = max(answer, depth)
  否则继续访问左右孩子

先固定深度定义：从当前节点到最远叶子的节点数。然后把每次递归想成孩子交给父节点的一张“深度回执”，父节点只需选择更大的回执并加上自己。

动画从叶子开始返回，让数字沿调用栈向上汇合。对比 left+right+1 的错误写法，可以看到相加计算的是跨过当前节点的两侧路径，不是单条向下路径。

• • 函数语义先于递推公式。
• • nil → 0 为叶子返回 1 提供自然基线。
• • max 表示选择更深的一侧，+1 表示计入当前节点。

定义 maxDepth(node) 的唯一职责：返回以 node 为根的子树最大深度。这个返回值必须已经是完整结论，父节点不需要知道孩子内部经过了哪些节点。

空节点返回 0。非空节点分别取得 left 和 right；根到叶路径从当前节点出发后只能进入其中一棵子树，因此选择 max(left,right)，再加 1 计入当前节点。

节点 20 的左、右孩子 15 和 7 都返回 1，所以 20 返回 2；根 3 收到左侧 1、右侧 2，最终返回 3。

递归进入节点后，先处理 nil 基线；随后分别调用左右孩子。只有孩子返回，当前节点才能比较 left 和 right 并生成自己的结果。

在 Go 实现中可用 if left > right 返回 left+1，否则返回 right+1。两边相等时任选一边都不影响结果。

• • 进入阶段负责拆分成左右两个同类子问题。
• • 返回阶段负责合并两个深度数字。
• • 系统调用栈保存尚未完成合并的祖先节点。
• • 链状树会让调用栈达到 O(n)，不能声称额外空间恒定。

第一步处理空节点；第二步递归计算左右深度；第三步返回较大深度加一。

这是后序语义：必须先得到孩子的答案，才能计算父节点。代码书写顺序本身就体现了依赖关系。

对树的结构做归纳。空树没有节点，深度为 0，基础情况正确。假设递归能够正确得到左右子树的最大深度 left 与 right。

从当前节点出发的任意根到叶路径，第一步要么进入左子树，要么进入右子树，不可能同时进入两边。因此最长路径的剩余部分长度是 max(left,right)。

再把当前节点计入，得到 max(left,right)+1。由结构归纳，函数对任意二叉树都返回正确最大深度。