题目
100. 相同的树
简单
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:p = [1,2,3], q = [1,2,3] 输出:true
示例 2:
输入:p = [1,2], q = [1,null,2] 输出:false
示例 3:
输入:p = [1,2,1], q = [1,1,2] 输出:false
提示:
- 两棵树上的节点数目都在范围
[0, 100]
内 -104 <= Node.val <= 104
思路和解题方法
bool isSameTree(TreeNode* p, TreeNode* q)
:这是一个名为isSameTree
的函数,它接受两个参数p
和q
,分别表示要比较的两个二叉树的根节点。返回值类型为bool
,表示两个二叉树是否相同。
if (p == nullptr && q == nullptr)
:首先判断两个节点p
和q
是否都为空。如果是,则表示这两个子树是相同的,没有节点需要比较,直接返回true
。
else if (p == nullptr || q == nullptr)
:如果只有一个节点为空,而另一个节点不为空,这说明这两个子树不相同,因为它们的节点数量不同。在此情况下,直接返回false
。
else if (p->val != q->val)
:如果两个节点都不为空,但它们的值不相同,说明这两个子树不相同,直接返回false
。
else
:当两个节点都不为空且它们的值相等时,我们需要进一步比较它们的左右子树。递归调用isSameTree
函数,传入左子树的左孩子和右子树的右孩子,以及左子树的右孩子和右子树的左孩子。只有当这两个递归调用都返回true
时,才说明整个树是相同的,返回true
。
复杂度
时间复杂度:
O(n。c)
时间复杂度是O(n),其中n表示两个二叉树中节点数的最大值。这个复杂度是因为在最坏情况下,需要访问两个二叉树的所有节点,因此时间复杂度是线性的。
空间复杂度
O(n)
空间复杂度也是O(n),由于递归调用,每个函数调用都会将一些数据压入堆栈中,因此需要O(n)的空间来存储这些信息(其中n表示树的高度)。在最坏情况下,两个树的高度相同,因此空间复杂度与节点数成正比。
c++ 代码
class Solution {
public:// 判断两个二叉树是否相同的函数bool isSameTree(TreeNode* p, TreeNode* q) {// 如果两个节点都是空,则表示这两个子树是相同的,直接返回trueif (p == nullptr && q == nullptr) {return true;} // 如果只有一个节点为空,则表示这两个子树不相同,直接返回falseelse if (p == nullptr || q == nullptr) {return false;} // 如果两个节点的值不相同,则表示这两个子树不相同,直接返回falseelse if (p->val != q->val) {return false;} // 递归比较左右子树的节点,只有左右子树的对应节点都相同时,// 才表示这两个子树相同,因此需要对两个子树递归调用此函数else {return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);}}
};
觉得有用的话可以点点赞,支持一下。
如果愿意的话关注一下。会对你有更多的帮助。
每天都会不定时更新哦 >人< 。