LeetCode 100. 相同的树(Same Tree):DFS 递归与 BFS 迭代双解法深度解析
LeetCode 100. 相同的树(Same Tree):DFS 递归与 BFS 迭代双解法深度解析
本文以 doocs/leetcode 仓库中 0100.Same Tree 题解文档为核心,系统讲解「相同的树」这一二叉树经典判定问题的完整解法:从题目定义与判定规则出发,给出 DFS 递归与 BFS 迭代两套可运行、可直接提交的代码实现(Python、Java、C++、Go、TypeScript、Rust、JavaScript、PHP),并结合仓库源码逐行拆解判定逻辑与复杂度。读完本文,你将掌握二叉树结构等价性判定的标准套路,并能熟练迁移到子树判定、对称树等同类问题。
题目定义:什么样的两棵树才算「相同」
给定两棵二叉树的根节点 p 和 q,编写函数判断它们是否相同。根据 README_EN.md 中的题目描述,两个二叉树相同当且仅当结构上完全一致,且对应位置节点的值相同。这里「结构上完全一致」是一个容易被忽略的要点——不仅两棵树要长得一样,null 子节点的位置也必须一一对应,任何一边多出一个节点都算不同。
判定规则的直观拆解
对任意一对待比较节点,可以归纳为三条互斥的判定规则:
- 两个节点均为
null:视为相同,返回true; - 仅其中一个为
null(或值不同):结构/取值不一致,返回false; - 两者均非空且值相等:继续递归/迭代比较左子树与右子树。
以上条件全部满足时,两棵树才相同。这一规则同时是 DFS 与 BFS 两种实现的核心逻辑基础。
示例演示
示例 1: p = [1,2,3],q = [1,2,3],输出 true——结构与值完全一致。
示例 2: p = [1,2],q = [1,null,2],输出 false——节点 2 在左树中是左孩子,在右树中却是右孩子,结构不同。
示例 3: p = [1,2,1],q = [1,1,2],输出 false——虽然节点值集合相同,但值 2 和 1 的位置错位,对应位置值不同。
数据范围与约束
根据文档约束(见 README_EN.md 的 Constraints 部分):
- 两棵树的节点数均在范围
[0, 100]内,即允许空树(p、q同时为空应返回true,仅一棵为空返回false); - 节点值范围
-10^4 <= Node.val <= 10^4。
节点数上限仅为 100,意味着递归深度可控、不会发生栈溢出,DFS 递归方案是安全且推荐的。
方法一:DFS 递归——同步遍历两棵树
算法思想
树由「根节点 + 左右子树」递归定义,因此判断两棵树是否相同,本质上是成对比较两棵树的对应节点。文档(README_EN.md 的 Solution 1 部分)给出的思路是:
- 若两棵树的根节点都为空,则两树相同;
- 若有且仅有一个根为空,则两树一定不同;
- 若两个根都不为空,先比较值:值不同则两树一定不同;值相同则继续判断左子树是否相同且右子树是否相同。
这个判断天然是递归的:isSameTree(p.left, q.left) 与 isSameTree(p.right, q.right) 的结果通过逻辑与(&& / and)组合。值得注意的一个优化细节:仓库中 Python、Java、C++、Go 的实现都先写了 p == q(或 if (p == q) return true)这一短路判断——当两个指针引用同一个对象时直接返回 true,既避免了无意义的递归,也是一种防御性写法。
各语言实现
以下实现均摘自 Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.rs 以及文档中对应的代码块,与文档完全一致。
Python3(Solution.py):
class Solution:
def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
if p == q:
return True
if p is None or q is None or p.val != q.val:
return False
return self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right)
Java(Solution.java):
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == q) return true;
if (p == null || q == null || p.val != q.val) return false;
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
C++(Solution.cpp):
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);
}
};
Go(Solution.go):
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == q {
return true
}
if p == nil || q == nil || p.Val != q.Val {
return false
}
return isSameTree(p.Left, q.Left) && isSameTree(p.Right, q.Right)
}
TypeScript(Solution.ts):
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
if (p == null && q == null) {
return true;
}
if (p == null || q == null || p.val !== q.val) {
return false;
}
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
JavaScript(Solution.js):
var isSameTree = function (p, q) {
if (!p && !q) return true;
if (p && q) {
return p.val === q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
return false;
};
PHP(Solution.php):
class Solution {
function isSameTree($p, $q) {
if ($p == null && $q == null) {
return true;
}
if ($p == null || $q == null) {
return false;
}
if ($p->val != $q->val) {
return false;
}
return $this->isSameTree($p->left, $q->left) && $this->isSameTree($p->right, $q->right);
}
}
Rust(Solution.rs): 由于 Rust 的 TreeNode 用 Option<Rc<RefCell<TreeNode>>> 表示,递归比较需要先通过 borrow() 获取节点的不可变引用再比较值:
impl Solution {
fn dfs(p: &Option<Rc<RefCell<TreeNode>>>, q: &Option<Rc<RefCell<TreeNode>>>) -> bool {
if p.is_none() && q.is_none() {
return true;
}
if p.is_none() || q.is_none() {
return false;
}
let r1 = p.as_ref().unwrap().borrow();
let r2 = q.as_ref().unwrap().borrow();
r1.val == r2.val && Self::dfs(&r1.left, &r2.left) && Self::dfs(&r1.right, &r2.right)
}
pub fn is_same_tree(
p: Option<Rc<RefCell<TreeNode>>>,
q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
Self::dfs(&p, &q)
}
}
Rust 版本把判定逻辑抽到私有辅助函数 dfs 中,主入口 is_same_tree 只负责转发引用,避免递归时反复移动所有权;同时利用 r1.val == r2.val && ... 的短路求值,在值不相等时立即终止,不再深入子树。
复杂度分析(DFS)
- 时间复杂度:
O(min(m, n)),其中m、n分别是两棵树的节点数。两棵树同步前进,一旦在某一对节点发现不一致就立即返回,因此最坏情况也只是完整访问较小的一棵树。 - 空间复杂度:
O(min(m, n)),主要取决于递归调用栈的层数。在链式(退化)二叉树的最坏情况下,递归深度等于节点数;由于两棵树结构一致,深度不会超过节点数较少的那棵树。在题目约束(节点数 ≤ 100)下,递归栈开销完全可接受。
方法二:BFS 迭代——双队列同步层序遍历
算法思想
DFS 方案的代价是消耗系统递归栈。文档(README_EN.md 的 Solution 2 部分)给出的迭代思路是:用两个队列分别承载两棵树的节点,成对取出、成对比较、成对入队,按层序同步推进。
具体比较流程:
- 将
p、q的根节点分别加入两个队列; - 每次从两个队列各取出一个节点
a、b:- 若
a.val != b.val,直接返回false; - 比较左右孩子的「存在性」:若一边有左孩子而另一边没有(
(la && !lb) || (lb && !la)),或右边同理,则结构不同,返回false; - 若左右孩子存在性一致,则把存在的对应孩子成对入队,进入下一轮;
- 若
- 当两个队列同时为空时,说明所有节点已比较完毕,返回
true。
这里的关键在于「存在性校验 + 成对入队」:空孩子不进入队列,因此队列中永远只有成对的非空节点,天然规避了 null 节点的比较问题。
各语言实现
以下实现摘自 Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.rs,均与文档代码一致。
Python3(Solution2.py):
class Solution:
def isSameTree(self, p: TreeNode, q: TreeNode) -> bool:
if p == q:
return True
if p is None or q is None:
return False
q1, q2 = deque([p]), deque([q])
while q1 and q2:
a, b = q1.popleft(), q2.popleft()
if a.val != b.val:
return False
la, ra = a.left, a.right
lb, rb = b.left, b.right
if (la and not lb) or (lb and not la):
return False
if (ra and not rb) or (rb and not ra):
return False
if la:
q1.append(la)
q2.append(lb)
if ra:
q1.append(ra)
q2.append(rb)
return True
Java(Solution2.java):
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == q) {
return true;
}
if (p == null || q == null) {
return false;
}
Deque<TreeNode> q1 = new ArrayDeque<>();
Deque<TreeNode> q2 = new ArrayDeque<>();
q1.offer(p);
q2.offer(q);
while (!q1.isEmpty() && !q2.isEmpty()) {
p = q1.poll();
q = q2.poll();
if (p.val != q.val) {
return false;
}
TreeNode la = p.left, ra = p.right;
TreeNode lb = q.left, rb = q.right;
if ((la != null && lb == null) || (lb != null && la == null)) {
return false;
}
if ((ra != null && rb == null) || (rb != null && ra == null)) {
return false;
}
if (la != null) {
q1.offer(la);
q2.offer(lb);
}
if (ra != null) {
q1.offer(ra);
q2.offer(rb);
}
}
return true;
}
}
C++(Solution2.cpp):
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if (p == q) return true;
if (!p || !q) return false;
queue<TreeNode*> q1{{p}};
queue<TreeNode*> q2{{q}};
while (!q1.empty() && !q2.empty()) {
p = q1.front();
q = q2.front();
if (p->val != q->val) return false;
q1.pop();
q2.pop();
TreeNode *la = p->left, *ra = p->right;
TreeNode *lb = q->left, *rb = q->right;
if ((la && !lb) || (lb && !la)) return false;
if ((ra && !rb) || (rb && !ra)) return false;
if (la) {
q1.push(la);
q2.push(lb);
}
if (ra) {
q1.push(ra);
q2.push(rb);
}
}
return true;
}
};
Go(Solution2.go): 使用切片模拟队列,出队通过切片截断 q1[1:] 实现:
func isSameTree(p *TreeNode, q *TreeNode) bool {
if p == q {
return true
}
if p == nil || q == nil {
return false
}
q1 := []*TreeNode{p}
q2 := []*TreeNode{q}
for len(q1) > 0 && len(q2) > 0 {
p, q = q1[0], q2[0]
if p.Val != q.Val {
return false
}
q1, q2 = q1[1:], q2[1:]
la, ra := p.Left, p.Right
lb, rb := q.Left, q.Right
if (la != nil && lb == nil) || (lb != nil && la == nil) {
return false
}
if (ra != nil && rb == nil) || (rb != nil && ra == nil) {
return false
}
if la != nil {
q1 = append(q1, la)
q2 = append(q2, lb)
}
if ra != nil {
q1 = append(q1, ra)
q2 = append(q2, rb)
}
}
return true
}
TypeScript(Solution2.ts): 该实现更紧凑,用单个队列成对存放两棵树的节点(先压入 p 的节点再压入 q 的对应节点,每次 shift() 两次取出成对节点):
function isSameTree(p: TreeNode | null, q: TreeNode | null): boolean {
const queue = [];
p && queue.push(p);
q && queue.push(q);
if (queue.length === 1) {
return false;
}
while (queue.length !== 0) {
const node1 = queue.shift();
const node2 = queue.shift();
if (node1.val !== node2.val) {
return false;
}
if (
(node1.left == null && node2.left != null) ||
(node1.left != null && node2.left == null)
) {
return false;
}
if (
(node1.right == null && node2.right != null) ||
(node1.right != null && node2.right == null)
) {
return false;
}
if (node1.left != null) {
queue.push(node1.left);
queue.push(node2.left);
}
if (node1.right != null) {
queue.push(node1.right);
queue.push(node2.right);
}
}
return true;
}
注意 TypeScript 版本入口处的处理:p、q 同时为空时队列长度为 0,直接进入 while 后返回 true;仅一个为空时队列长度为 1,提前返回 false。这与其他语言「先判空再入队」的写法等价。
Rust(Solution2.rs): 与 TypeScript 类似的单队列成对策略,借助 VecDeque 实现双端队列,并用 match 模式匹配对左右孩子的存在性进行分支处理:
impl Solution {
pub fn is_same_tree(
mut p: Option<Rc<RefCell<TreeNode>>>,
mut q: Option<Rc<RefCell<TreeNode>>>,
) -> bool {
let mut queue = VecDeque::new();
if p.is_some() {
queue.push_back(p.take());
}
if q.is_some() {
queue.push_back(q.take());
}
if queue.len() == 1 {
return false;
}
while queue.len() != 0 {
if let (Some(mut node1), Some(mut node2)) = (queue.pop_front(), queue.pop_front()) {
let mut node1 = node1.as_mut().unwrap().borrow_mut();
let mut node2 = node2.as_mut().unwrap().borrow_mut();
if node1.val != node2.val {
return false;
}
match (node1.left.is_some(), node2.left.is_some()) {
(false, false) => {}
(true, true) => {
queue.push_back(node1.left.take());
queue.push_back(node2.left.take());
}
(_, _) => {
return false;
}
}
match (node1.right.is_some(), node2.right.is_some()) {
(false, false) => {}
(true, true) => {
queue.push_back(node1.right.take());
queue.push_back(node2.right.take());
}
(_, _) => {
return false;
}
}
}
}
true
}
}
复杂度分析(BFS)
- 时间复杂度:
O(min(m, n))。与 DFS 相同,两棵树成对同步遍历,任一时刻发现不一致立即返回。 - 空间复杂度:
O(min(m, n))。空间取决于队列中的元素个数;同一层入队的节点对数量不会超过较小树的节点总数。相比 DFS 的递归栈,BFS 在极端链式树上不会产生深栈,但队列在满二叉树的最宽层也会达到O(n)量级,两者渐近复杂度一致。
两种方法对比与选型建议
| 维度 | DFS 递归 | BFS 迭代 |
|---|---|---|
| 遍历顺序 | 深度优先(先根,再左/右子树) | 广度优先(按层成对比较) |
| 数据结构 | 系统调用栈 | 显式队列(双队列或单队列成对存放) |
| 时间复杂度 | O(min(m, n)) |
O(min(m, n)) |
| 空间复杂度 | O(min(m, n))(递归栈) |
O(min(m, n))(队列) |
| 提前终止 | 值不等/结构不等时立即返回 | 同左 |
| 适合场景 | 实现简洁、易读;节点规模不大时首选 | 避免递归深度问题;面试考察迭代写法时 |
选型建议: 在本题约束(节点数 ≤ 100)下两种方案均无性能风险,优先推荐 DFS 递归——代码更短、语义更贴合「树是递归结构」的本质;如果面试官要求写出非递归版本,或树可能极深(如退化链表形态且节点数很大),则采用 BFS 迭代更稳妥。
仓库中的代码组织:从题解文档到可提交文件
在 doocs/leetcode 仓库中,本题目录 solution/0100-0199/0100.Same Tree 采用「文档 + 独立源码文件」双轨组织:
- 题解文档: README.md(中文)与 README_EN.md(英文),包含题目描述、示例图与完整解法说明;
- 解法一源码:
Solution.py、Solution.java、Solution.cpp、Solution.go、Solution.ts、Solution.js、Solution.php、Solution.rs——对应 DFS 递归实现,文件内容与文档代码块完全一致; - 解法二源码:
Solution2.py、Solution2.java、Solution2.cpp、Solution2.go、Solution2.ts、Solution2.rs——对应 BFS 迭代实现; - 示例图: images/ex1.jpg、images/ex2.jpg、images/ex3.jpg 展示了三个输入输出示例的树形结构。
这种「一题多解、一解多语言」的布局意味着:无论你使用哪种语言准备面试,都可以直接在对应 Solution*. 文件中找到可直接提交的完整代码,并以文档中的复杂度分析作为复习要点。
思维拓展:从「相同树」到同类树问题
「相同的树」的判定框架可以顺滑迁移到一批经典二叉树问题,理解其判定规则后能事半功倍:
- 判断一棵树是否为另一棵树的子树(Subtree of Another Tree):对主树的每个节点调用「两树相同」判断,即可转化为本问题的组合应用;
- 对称二叉树(Symmetric Tree):将一棵树的左子树与右子树互为镜像比较,比较逻辑与本问题高度相似,只是孩子配对方向相反(左对右、右对左);
- 判断两棵树结构是否一致但值可不同:只需把「值比较」去掉,保留结构与存在性判断,即可衍生出「同构(isomorphic)树」变体。
掌握本文的成对比较思想(p、q 同步前进 + 空值处理 + 短路返回),就掌握了这一系列树问题的最小公共核心。
小结
LeetCode 100. 相同的树是一道「高频且基础」的二叉树入门题,考察的是对递归/迭代遍历的掌握与边界条件(空节点)处理。doocs/leetcode 仓库为本题提供了两种解法、八种语言的完整实现:DFS 递归版代码简洁、语义直观;BFS 迭代版避免了调用栈依赖,适合考察非递归写法的场景。两者时间复杂度均为 O(min(m, n)),空间复杂度均为 O(min(m, n))。建议对照 Solution.py 与 Solution2.py 各默写一遍,再尝试迁移到子树判定与对称树问题,即可彻底吃透这一类树的等价性判定。