第5章｜二叉树与递归

Unit 01 · LeetCode #104 二叉树的最大深度

← Unit 00 基础

仅本次页面有效

104

Maximum DepthTree · DFS · Recursion

不保存所有完整路径，
让每棵子树只返回一个深度。

最大深度表面上是在寻找最长根到叶路径；递归表示则把路径信息压缩为子树返回值。左右子树各返回一个整数，当前节点只做一次局部组合。

已恢复上次学习位置阶段、动画、答题、代码和迁移进度均已恢复。

Unit 00 概念桥｜本页只保留后续真正会用到的四个概念不单独增加学习环节

子树

以某个节点为根，包含其全部后代的完整结构。

函数契约

每次调用都承诺：返回当前完整子树的最大深度。

Base Case

空树返回 0，使叶子可以通过 1 + max(0,0) 得到 1。

调用栈

父调用暂停等待子调用，返回值出现后再恢复组合。

LeetCode #104 原题题面转述、示例与复杂度

题目要求

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

class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: pass

约束

节点数量范围为 [0, 10⁴]；
-100 ≤ Node.val ≤ 100。

示例

输入：root = [3,9,20,null,null,15,7]
输出：3

输入：root = [1,null,2]
输出：2

主方法

递归 DFS：每个节点访问一次，时间复杂度 O(n)；递归栈空间为 O(h)。

官方示例树状态 1 / 1

当前函数契约

当前 node—

当前阶段—

left_depth—

right_depth—

调用栈（顶部为当前函数）

当前状态未进入递归栈

已产生的子树返回值

暂无

请先观察当前动画状态，再作答。

槽位拼接：只补关键递归表达式不是从空白写完整函数

class Solution: def maxDepth(self, root: Optional[TreeNode]) -> int: if : return left_depth = right_depth = return

from typing import Optional

class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

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

        return 1 + max(left_depth, right_depth)

代码—树—调用栈—返回值联动问题随当前轨迹变化

当前 node—

阶段—

left_depth—

right_depth—

调用栈0

返回值—

当前轨迹问题

请先移动轨迹，再根据当前调用栈作答。

完成代码槽位并看懂至少一个“父帧等待”状态后，再进入迁移当前仍可继续观察轨迹；页面不会自动跳转。

迁移目标：LeetCode #111 二叉树的最小深度

不从空白直接写代码。先复用 #104 的“子树返回值契约”，再用单孩子反例识别新增边界，完成槽位拼接，最后运行真实轨迹并在可调整编辑器中完成代码。

LeetCode #111｜二叉树的最小深度

Minimum Depth of Binary Tree · Tree · DFS · BFS

简单

迁移原题

给定二叉树根节点 root，返回从根节点到最近叶子节点的最短路径上的节点数量。叶子节点是没有左右孩子的节点。

class Solution: def minDepth(self, root: Optional[TreeNode]) -> int: pass

原题入口：LeetCode #111

示例与约束

输入：root = [3,9,20,null,null,15,7]
输出：2

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

节点数量范围为 [0, 10⁵]，节点值范围为 [-1000,1000]。

复用函数契约，不能机械替换 `max` 为 `min`

#104 已掌握

maxDepth(node) 返回当前子树到最远叶子的节点数；父节点只接收左右两个整数。

→

#111 继续使用

minDepth(node) 仍返回当前子树答案，但目标改为“最近的真正叶子”。

迁移中的新变量不是更多代码，而是“这个 0 是否代表一条有效的根到叶路径”。

反例：[1, null, 2] 中，空分支返回 0，但它不是叶子路径

left_depth0（数值存在，但路径无效）

right_depth1（到节点 2 的有效路径）

错误公式1 + min(0,1) = 1

正确处理只有右孩子 → 1 + minDepth(root.right) = 2

当前红色虚线分支为什么不能参与 `min`？

必须依据图中的“None 不是叶子”状态回答。

将 7 个代码片段放入正确的结构顺序

槽位表示四类结构：空树、只有右孩子、只有左孩子、左右孩子都存在。先点击片段，再点击槽位。

代码片段

执行顺序

运行单孩子轨迹，再在完整编辑器中验证迁移

当前 node—

分支类型—

left_depth—

right_depth—

返回值—

有效路径—

完整迁移代码编辑器默认 460px，可拖动、增高、自动适应与全屏

参考答案框高度独立保存

from typing import Optional

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0

        if root.left is None:
            return 1 + self.minDepth(root.right)

        if root.right is None:
            return 1 + self.minDepth(root.left)

        left_depth = self.minDepth(root.left)
        right_depth = self.minDepth(root.right)
        return 1 + min(left_depth, right_depth)

Unit 01 Skill 卡｜六个主环节到此结束

真正可迁移的不是 1 + max(...) 这行表面公式，而是“定义子树返回值 → 让子调用完成内部工作 → 当前节点局部组合”的递归建模方式。#111 新增的是有效路径判断。

题型信号答案可由左右子树同类答案组合

函数契约返回当前完整子树的最大深度

Base Case空树返回 0

组合规则1 + max(left_depth,right_depth)

复杂度时间 O(n)，栈空间 O(h)

迁移警报最小深度需排除无效空分支

迁移已完成，本页不会自动跳走

可以继续停留查看轨迹、修改代码，或使用上方六段导航返回任一环节。

完成当前状态题后手动继续；页面不会自动跳转。

不保存所有完整路径，让每棵子树只返回一个深度。

题目要求

约束

示例

主方法

调用栈（顶部为当前函数）

已产生的子树返回值

当前轨迹问题

迁移目标：LeetCode #111 二叉树的最小深度

LeetCode #111｜二叉树的最小深度

迁移原题

示例与约束

复用函数契约，不能机械替换 max 为 min

反例：[1, null, 2] 中，空分支返回 0，但它不是叶子路径

当前红色虚线分支为什么不能参与 min？

将 7 个代码片段放入正确的结构顺序

代码片段

执行顺序

运行单孩子轨迹，再在完整编辑器中验证迁移

Unit 01 Skill 卡｜六个主环节到此结束

不保存所有完整路径，
让每棵子树只返回一个深度。

复用函数契约，不能机械替换 `max` 为 `min`

当前红色虚线分支为什么不能参与 `min`？