相同的树 | 每日算法 · 变量语义法

🎧 语音讲解

开车或通勤时可听，跟着思路走一遍

速度

📋 题目描述

给你两棵二叉树的根节点 p 和 q，编写一个函数来检验这两棵树是否相同。

如果两棵树在结构上相同，并且对应节点具有相同的值，则认为它们是相同的。

节点数目在 [0, 100]，节点值在 32 位有符号整数范围内。

示例 1

输入：p = [1,2,3], q = [1,2,3]

输出：true

示例 2

输入：p = [1,2], q = [1,null,2]

输出：false

p 的右子树为空，q 的右子树有节点 2，结构不同。

示例 3

输入：p = [1,2,1], q = [1,1,2]

输出：false

左右孩子位置对调，结构不同。

💭 模拟答题者思考

1. 暴力直觉：把两棵树分别中序/前序序列化再比较字符串——能判值序列，但结构信息容易丢（例如示例 2 的 null 位置），还要额外编码空指针，不如直接同步走树。

2. 重复在哪里？「是否相同」在每一对对齐节点上问的是同一句话：值是否相等、左子树是否相同、右子树是否相同——子问题与整题同型，天然递归。

3. 同步 DFS：若 p、q 都空 → true；仅一方空 → false；值不等 → false；否则答案 = 左对左 AND 右对右。

4. 示例 2：p=[1,2] 在根处左孩子都是 2，但 p.right 为空而 q.right 为 2，在右子树对齐时「一空一非空」，直接假。

5. 每个节点访问常数次，时间 O(n)；递归深度 O(h)，链状树最坏 O(n)。BFS 双队列同步出队是同一逻辑的迭代写法。

🧠 变量语义（先读这三句再编码）

变量	类型	语义（三句法）
`p` / `q`	TreeNode*	定义：当前正在对齐比较的两棵树的「同步根」维护：每次递归/迭代都同时指向结构上一一对应的节点；若一方为空另一方非空则已可判假更新：处理完当前层后，`p,q` 分别移向各自的 `left`，再移向各自的 `right`
`dfs(p,q)`	bool	定义：以 `p`、`q` 为根的子树是否完全相同维护：真当且仅当当前节点值相等且左右子树分别相同；空对空为真更新：`return dfs(p.left,q.left) and dfs(p.right,q.right)`（值不等或一空一非空时短路为假）

⌨️ 落码步骤

1. 若 p 与 q 均为空，返回 true

2. 若仅一方为空，或 p.val != q.val，返回 false

3. 返回 isSameTree(p.left, q.left) and isSameTree(p.right, q.right)

4. （迭代备选）双队列同时入队根；循环中成对弹出，判空与值，再把左右孩子成对入队

💻 代码实现

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

# 迭代（双队列同步）：
# from collections import deque
# def isSameTree(self, p, q):
#     qp, qq = deque([p]), deque([q])
#     while qp:
#         a, b = qp.popleft(), qq.popleft()
#         if not a and not b: continue
#         if not a or not b or a.val != b.val: return False
#         qp.append(a.left); qq.append(b.left)
#         qp.append(a.right); qq.append(b.right)
#     return True

class Solution {
public:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if (!p && !q) return true;
        if (!p || !q || p->val != q->val) return false;
        return isSameTree(p->left, q->left)
            && isSameTree(p->right, q->right);
    }
};
// 时间 O(n)，空间 O(h)

📈 复杂度分析

时间复杂度 O(n)

空间复杂度 O(h)（递归栈，h 为树高；BFS 队列同理）

⚠️ 常见坑

❗ 只比较值、不比较空指针：必须「双空为真、一空一假为假」，不能只写 p.val == q.val。

❗ 左右子树对错配对：必须是 (p.left, q.left) 与 (p.right, q.right)，不能写成 p.left 对 q.right（示例 3 会误判）。

❗ BFS 时只用一个队列交替存两棵树：应双队列或队列存 pair，保证每一层节点成对比较。

🔍 必测边界 Case

Case 1：两棵都空

p = null, q = null → true

Case 2：一空一非空

p = [1], q = [] → false

Case 3：单节点值相同

p = [1], q = [1] → true

Case 4：结构不同（官方示例 2）

p = [1,2], q = [1,null,2] → false