LeetCode 100简单二叉树 · 递归
相同的树 图解题解
两棵树结构和值完全相同？递归让每个节点自己回答这个问题。
两张家谱对照看是否一模一样：站在根节点，先比这两人名字，不同立刻否；相同再让左子树和右子树各自去对照——同一套规则递归铺下去。遇到两边都空说明这支对上了，一空一非说明结构不同，任一层不过就整体不同。每个节点只做一次比较，O(n) 走完。
这道题到底在问什么
判断两棵树结构和值是否完全相同。
- p
- [1,2,3]
- q
- [1,2,3]
- 输出
- true
最优解：一步一步想明白
- 3关键不是背模板，而是看懂为什么这题适合二叉树 · 递归。
- 4约定：下面这棵树画的是 p，queue 同步报出 q 在对应位置的值，逐点对比。isSameTree 三道关卡：①都空→相同 ②一空一非→不同 ③值不等→不同 ④值相等→递归左右。根：p=1、q=1，相等。
- 5根相等，递归比较左孩子：p.left=2、q.left=2，相等。
- 6继续深入节点 2 的孩子：p、q 都是空 → 命中“都空 → 相同”，这一支返回 true。
- 7回到根，递归比较右孩子：p.right=3、q.right=3，相等。
- 8所有对应节点都相等、结构一致 → isSameTree 返回 true。
- 9反例：queue 报出 q 这个位置是 4，而 p 是 3 → 3 ≠ 4，立刻 return false，不必再比其它。（红节点 = p、q 在此处值不一致）
- 10另一种 false：p 这里有节点 2、q 对应位置是空 → 一空一非空 → false。（这里红节点 = p、q 在此处结构不一致：一边有、一边空）
- 13把这句话记住，下次遇到同类题，就能更快选出方向。
⚠️ 容易写错的地方
✗ 错：只比较遍历值序列
✓ 对：结构也必须完全相同
不同结构可能有相同遍历片段
✗ 错：没先判空就访问 .val
✓ 对：先处理两节点的空/非空组合
空节点没有 val，直接比会空指针；必须先把“都空/一空一非”两种出口判掉。
✗ 错：变量名和动画不一致
✓ 对：代码变量沿用动画里的核心名字
学习时最怕脑内维护两套概念
完整代码（Python / C++ / Java）
Python
class Solution:
def isSameTree(self, p, q):
if not p and not q:
return True
if not p or not q:
return False
if p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)C++
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (!p && !q) return true; // 都空
if (!p || !q) return false; // 一空一非
if (p->val != q->val) return false; // 值不等
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
};Java
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null && q == null) return true; // 都空
if (p == null || q == null) return false; // 一空一非
if (p.val != q.val) return false; // 值不等
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}套路模板 · 二叉树 · 递归
# 双树同步递归骨架（相同/对称/子树通用）
def f(a, b):
if not a and not b: return True # 两边都空
if not a or not b: return False # 一边空 → 不匹配
if a.val != b.val: return False # 值不符
# 按题意配对递归：相同→左对左/右对右；对称→左对右/右对左
return f(a.left, b.left) and f(a.right, b.right)复杂度
时间复杂度
O(min(m, n))
每对对应节点最多比一次，O(min(m, n))
空间复杂度
O(h)
递归栈深度 = 树高 h
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 相同的树 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和「对称二叉树 LC101」差在哪？+
相同树是平行比较(a.left vs b.left)；对称是交叉比较(a.left vs b.right)。
为什么先判空再比值？+
空节点没有 val，必须先处理两节点的空/非空组合，避免空指针。
复杂度？+
O(min(m,n)) 时间、O(h) 递归栈。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。