第5章｜二叉树与递归

Unit 04 · LeetCode #100 相同的树

← Unit 03

仅本次页面有效

U04

Same TreePair · Structure · Same Direction

相同不是“遍历值一样”，
而是每个对应位置同时相同。

两棵树必须同步推进：对应位置同时为空，或同时存在且节点值相等；随后继续比较左对左、右对右。任何一个位置失败，整棵树立即失败。

已恢复上次学习位置当前环节、轨迹、代码、迁移槽位和编辑器高度已恢复。

知识桥梁｜Unit 03 → Unit 04

上一题：镜像关系

left.left ↔ right.right，方向会在中心轴两侧反转。

保留双节点骨架 →

本题：对应关系

p.left ↔ q.left，两个位置沿完全相同的左右路径同步推进。

本单元唯一需要重新审查的维度Base Case 与值判断可以复用；递归配对方向决定你判断的是“镜像”还是“相同”。

LeetCode #100 原题题面、示例与复杂度

题目要求

给定两棵二叉树的根节点 p 和 q，判断它们是否相同。两棵树相同，当且仅当结构完全一致，并且对应节点具有相同的值。

class Solution: def isSameTree( self, p: Optional[TreeNode], q: Optional[TreeNode] ) -> bool: pass

两棵树节点数量均在 [0,100] 范围内；
-10⁴ ≤ Node.val ≤ 10⁴。

示例

p = [1,2,3], q = [1,2,3]
输出：true

p = [1,2], q = [1,null,2]
输出：false

p = [1,2,1], q = [1,1,2]
输出：false

双节点递归 DFS：每个对应位置最多检查一次，时间复杂度 O(n)，递归栈空间 O(h)。

对应位置

从两棵树根节点出发，沿相同的左右路径到达的位置。

双空

两个对应位置都为 None，说明该分支结构同步结束。

单空

只有一个位置为空，结构立即不一致，不能访问 val。

短路

左子树已经不同后，不再执行右子树比较。

两棵树的对应位置观察当前紫色连接线

Tree p

Tree q

绿色：已验证橙色：当前对应位置红色：结构或值失败

忽略 None 会丢失树结构

当前两棵树的非空先序值都为 [1,2]，但节点 2 位于不同方向。

忽略 None

保留 None

当前与后续节点对

递归函数契约isSameTree(p, q) 判断以 p、q 为根的完整子树是否完全相同。

当前 p—

当前 q—

存在性 / 值—

下一步—

当前返回—

关系方向左对左，右对右

调用栈（顶部为当前比较）

尚未进入递归轨迹

观察当前动画状态后回答

先观察高亮节点、None 位置和右侧状态。

运行案例：切换案例会保留当前学习环节。

显式短路版本代码1 / 1

当前运行状态动画只呈现代码无法静态表达的等待与短路

当前 p / q—

结构判断—

值判断—

left_same—

右子树是否执行—

返回结果—

进入函数。

用 8 个语义槽位编译主代码只填写必要表达式，不从空白默写整段

class Solution: def isSameTree(self, p, q) -> bool: if : return if : return if : return return ( and )

提示 1｜先处理结构边界
p 与 q 都为空时返回 True；恰有一侧为空时返回 False。

提示 2｜再处理当前节点
确认两侧都存在后，比较 p.val 与 q.val。

提示 3｜保持方向不变
左子问题：self.isSameTree(p.left, q.left)
右子问题：self.isSameTree(p.right, q.right)

槽位正确后会显示完整参考代码。

为什么不在这里重复播放动画？运行轨迹已经在上一环节完成

流程自适应本题的动画价值在“父调用等待 left_same、单空后跳过右子树”。代码环节只承担从状态规则到语法槽位的编译，不再复制同一轨迹。

提交前审查清单

① 先判断双空；② 再判断单空；③ 两侧非空后才能访问 val；④ 左对左、右对右；⑤ 两个递归结果用 and 组合。

class Solution:
    def isSameTree(self, p, q) -> bool:
        if p is None and q is None:
            return True
        if p is None or q is None:
            return False
        if p.val != q.val:
            return False

        return (
            self.isSameTree(p.left, q.left)
            and self.isSameTree(p.right, q.right)
        )

主代码正确后进入迁移 #572#572 不会要求你重新发明“相同树”；只新增在大树中搜索候选根的外层递归。

迁移目标：LeetCode #572 另一棵树的子树

把 #100 的 same_tree 当作局部验证器；外层递归只负责依次尝试当前节点、左子树和右子树。迁移增量是“搜索候选起点”，不是重新学习树相等。

LeetCode #572｜另一棵树的子树

标签：树 · 深度优先搜索 · 字符串匹配

简单

迁移原题

给定两棵二叉树 root 和 subRoot，检验 root 中是否存在一个节点，使得以该节点为根的子树与 subRoot 具有相同结构和节点值。

class Solution: def isSubtree( self, root: Optional[TreeNode], subRoot: Optional[TreeNode] ) -> bool: pass

打开 LeetCode 原题 ↗

示例

root = [3,4,5,1,2], subRoot = [4,1,2]
输出：true

root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出：false

核心结构：当前候选相同 OR 左侧找到 OR 右侧找到。

复用完整相等判断，只新增候选根搜索

#100 已掌握

same_tree(p,q) 可以准确验证两个给定根开始的完整子树是否相同。

作为子程序
嵌入搜索

#572 新任务

若当前 root 不是候选答案，不能直接 False；还要在 root.left 与 root.right 继续寻找。

当前候选 root=3、subRoot=4，same_tree 返回 False。外层函数下一步应该做什么？

区分“当前候选失败”与“整棵大树搜索失败”。

两个递归层次必须保持职责分离

层次	输入	返回含义	失败后动作
局部验证器	p, q	这两个根开始的树是否完全相同	返回 False
候选搜索器	root, subRoot	root 范围内是否存在匹配子树	继续搜索左右子树

候选 1root=3 → 不相同

候选 2root.left=4 → 验证中

候选 3root.right=5 → 尚未执行

当前候选 root=4 与 subRoot=4 已由 same_tree 验证为 True，应返回什么？

一旦找到匹配候选，or 会短路，不再搜索其他位置。

只拼接“外层搜索器”，same_tree 已作为可靠脚手架提供

片段库

isSubtree 外层骨架

观察“当前候选失败后继续搜索”的不可替代状态

当前候选 root3

same_tree 结果False

搜索动作转向左子树

最终返回—

先用 root=3 尝试匹配 subRoot=4。

参考答案可继续编辑和复制

class Solution:
    def isSubtree(self, root: Optional[TreeNode], subRoot: Optional[TreeNode]) -> bool:
        def same_tree(p, q):
            if p is None and q is None:
                return True
            if p is None or q is None:
                return False
            return (
                p.val == q.val
                and same_tree(p.left, q.left)
                and same_tree(p.right, q.right)
            )

        if root is None:
            return False

        return (
            same_tree(root, subRoot)
            or self.isSubtree(root.left, subRoot)
            or self.isSubtree(root.right, subRoot)
        )

Unit 04 Skill 卡

相同树把两棵树转写为同步的“对应位置节点对”。迁移到子树搜索时，#100 成为局部验证器，新增的外层递归只负责枚举候选根。两个递归层次必须各自保持单一职责。

核心契约isSameTree(p,q) 判断完整子树是否相同

结构边界双空为真，单空为假

配对方向左对左，右对右

短路行为首个结构或值差异即可失败

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

迁移模式局部验证器 + 候选位置搜索器

本状态已完成

请先停留观察高亮节点与返回值，确认你能解释为什么当前判断成立或失败。

环节 1 / 6