019 · Maximum Depth of Binary Tree

My First Thoughts

看到这题，目标是求二叉树的最大深度。

第一反应会很自然：

那是不是从 root 一直往下走，边走边累计次数就行？

比如可以先想几个变量：

depth = 0
left = 0
right = 0

然后从 root 出发：

• 如果 root 是 None，深度就是 0
• 如果 root 不是 None，至少有当前这个节点，所以深度应该从 1 开始
• 接着看 root.left
• 再看 root.right

这个方向是对的：深度确实是在沿着树往下走的过程中产生的。

但如果继续用 left += 1、right += 1 这种方式，很快就会乱掉。

因为树不是一条直线。每个节点下面又可能有左子树和右子树，而左子树里面也可能继续分叉。只靠外面的几个变量，很难清楚地表达：

当前节点下面的左子树有多深？右子树有多深？我要取哪一个？

所以这题更适合换一个角度看。

一个容易写出的递归雏形是：从当前节点继续递归左右子树，然后试着把深度加一。这个想法已经接近答案，但还缺少一步：递归调用必须返回左右子树各自的深度，再从里面取更大的那个。

---

Why That Is Not Enough

单纯“往下走并累计次数”不够，是因为每个节点都可能分成左右两条路。

我们真正需要知道的是：

• 左子树的最大深度是多少
• 右子树的最大深度是多少

然后当前节点的答案才是：

当前节点的最大深度 = 1 + max(左子树最大深度, 右子树最大深度)

这里的 1 表示当前节点自己，max(...) 表示只保留更深的那条路。

---

Final Idea

用递归解决这道题。

对于任意一个节点来说，它的最大深度只取决于两件事：

左子树的最大深度
右子树的最大深度

如果我们已经知道这两个值，那么当前节点的最大深度就是：

1 + max(左子树深度, 右子树深度)

所以递归函数可以定义成：

maxDepth(root) 返回以 root 为根节点的这棵树的最大深度。

递归终止条件：

if root is None:
    return 0

递归拆分：

left_depth = maxDepth(root.left)
right_depth = maxDepth(root.right)

合并答案：

return 1 + max(left_depth, right_depth)

以示例树为例：

        3
       / \
      9  20
        /  \
       15   7

递归关系可以这样看：

maxDepth(3)
├── maxDepth(9)  = 1
└── maxDepth(20)
    ├── maxDepth(15) = 1
    └── maxDepth(7)  = 1
    => 1 + max(1, 1) = 2

=> 1 + max(1, 2) = 3

所以整棵树的最大深度是 3。

---

Why It Works

树本身就是递归结构：

一棵树 = 一个根节点 + 一棵左子树 + 一棵右子树

要求整棵树的最大深度，本质上就是先求左右子树的最大深度，再把当前节点算进去。

递归函数 maxDepth(root) 的含义非常明确：

• 如果 root 是空，返回 0
• 如果 root 不是空，分别求左右子树深度
• 当前节点贡献 1
• 左右子树只保留更深的那一边

因为每个节点的答案都由它的左右子树答案推出，所以整棵树最终也能得到正确答案。

---

Code

def maxDepth(root):
    if root is None:
        return 0

    left_depth = maxDepth(root.left)
    right_depth = maxDepth(root.right)

    return 1 + max(left_depth, right_depth)

---

Complexity

Time	\(O(n)\) — 每个节点恰好被访问一次
Space	\(O(h)\) — 递归调用栈的深度等于树的高度 h，最坏情况下（树退化成一条链）是 \(O(n)\)

---

Takeaway

求二叉树最大深度时，不要用一个外部变量硬凑计数。更清楚的递归定义是：一个节点的最大深度，等于 1 + max(左子树深度, 右子树深度)。当前节点只贡献 1，真正的深度来自左右子树返回的结果。

---

← Quiz