相同的树
766 字
4 分钟
相同的树
- 难度：简单
- 标签：树、深度优先搜索、二叉树
题目描述
Note
原题说明：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在 结构上相同，并且节点具有 相同的值，则认为它们是相同的。
示例 1
两棵树完全相同（返回 true）
graph TD
subgraph Tree_P [Tree P]
p1((1)) --> p2((2))
p1((1)) --> p3((3))
end
subgraph Tree_Q [Tree Q]
q1((1)) --> q2((2))
q1((1)) --> q3((3))
end
结构不同（示例 2，返回 false）
graph TD
subgraph Tree_P2 [Tree P]
p1((1)) --> p2((2))
p1((1)) --- null1[null]
style null1 fill:none,stroke:none
end
subgraph Tree_Q2 [Tree Q]
q1((1)) --- null2[null]
q1((1)) --> q2((2))
style null2 fill:none,stroke:none
end
数值不同（示例 3，返回 false）
graph TD
subgraph Tree_P3 [Tree P]
p1((1)) --> p2((2))
p1((1)) --> p3((1))
end
subgraph Tree_Q3 [Tree Q]
q1((1)) --> q2((1))
q1((1)) --> q3((2))
end
方案一：递归 DFS（最优雅）
核心思路： 判断两棵树是否相同，可以拆解为三个条件：
- 根节点的值是否相同。
- 左子树是否相同。
- 右子树是否相同。 这三个条件必须同时满足（逻辑与关系）。
源码实现
class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { // 1. 基本情况：都为空，说明这一分支匹配成功 if (!p && !q) return true;
// 2. 异常情况：一个空一个不空，或者值不同，匹配失败 if (!p || !q || p->val != q->val) return false;
// 3. 递归：只有左右子树都对齐，整棵树才相同 return isSameTree(p->left, q->left) && isSameTree(p->right, q->right); }};复杂度分析
- 时间复杂度：。其中 是节点数较少的那棵树的节点数。每个节点最多被访问一次。
- 空间复杂度：。 是树的高度，主要消耗在系统递归栈上。
方案二：迭代 DFS（手动维护栈）
核心思路：
使用栈（stack）来模拟递归过程。我们将两棵树中位置对应的节点成对存入栈中，每次弹出一对进行比对。
源码实现
#include <stack>#include <utility>
class Solution {public: bool isSameTree(TreeNode* p, TreeNode* q) { // 使用 pair 存储待比较的两个节点对 stack<pair<TreeNode*, TreeNode*>> st; st.push({p, q});
while (!st.empty()) { auto [a, b] = st.top(); st.pop();
if (!a && !b) continue; // 都为空，继续检查其他分支 if (!a || !b || a->val != b->val) return false;
// 将对应的左右子树成对入栈 st.push({a->left, b->left}); st.push({a->right, b->right}); } return true; }};总结
- 结构与数值的双重校验：在树的算法中，
!p || !q这种判断是处理递归边界的“标准起手式”。 - 递归的魅力：在树结构中，递归往往能以极少的代码行数表达出极为复杂的逻辑。
- 与 101 题（对称二叉树）的联系：本题判断的是两棵树“一模一样”，而 101 题判断的是一棵树“镜像对称”，两者的核心思想高度一致。
Tip
树的比较类问题，本质上都是在进行某种形式的遍历。只要掌握了 DFS，所有关于“相等”、“镜像”、“包含”的问题都能迎刃而解！
文章分享
如果这篇文章对你有帮助，欢迎分享给更多人！
最后更新于 2025-10-25，距今已过 186 天
部分内容可能已过时
相关文章 智能推荐
1
二叉树的最大深度
算法 力扣第104题：二叉树的最大深度。深入理解递归与广度优先搜索（BFS）在计算树结构深度时的应用场景。
2
二叉树的中序遍历
算法 力扣第94题：二叉树的中序遍历。从递归的简洁到迭代的深度剖析，掌握树结构遍历的核心逻辑。
3
对称二叉树
算法 力扣第101题：对称二叉树。深入理解树的镜像对称性质，掌握递归与迭代两种姿势下的双向比对技巧。
4
二叉树的层序遍历
算法 力扣第102题：二叉树的层序遍历。掌握广度优先搜索（BFS）的核心机制，学习如何按层级剥开树结构的逻辑脉络。
5
二叉树的层序遍历 II
算法 力扣第107题：二叉树的层序遍历 II。在层序遍历的基础上，学习如何通过简单的结果反转实现自底向上的层级展示。
随机文章 随机推荐
评论区
欢迎来到我的博客！
音乐
暂未播放
0:00 0:00
119
11
346
226,548
0 天
0 天前