LeetCode———100——相同的树

简介: LeetCode———100——相同的树

1.题目


. - 力扣(LeetCode)


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


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


示例 1:

image.png



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

输出:true

示例 2:


image.png


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

输出:false

示例 3:


image.png


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

输出:false

提示:


两棵树上的节点数目都在范围 [0, 100] 内

-104 <= Node.val <= 104

2.解答


首先,我们判断两个节点p和q是否都为空,如果是,则表示当前子树相同,返回true。

然后,我们判断p和q是否有一个为空,如果是,则表示当前子树不相同,返回false。

最后,我们判断p和q的值是否相等,如果不相等,则表示当前子树不相同,返回false。

然后,我们递归判断p的左子树和q的左子树的相同性,以及p的右子树和q的右子树的相同性。

最终,如果所有子树都相同,返回true,否则返回false。

这种方法的时间复杂度是O(n),其中n是两个二叉树中节点的个数。


bool isSameTree(struct TreeNode* p, struct 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);
}

image.png

相关文章
|
6天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
6天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
6天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
10天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
11天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
18天前
|
算法 C语言 容器
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(下)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
31 7
|
18天前
|
C语言
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(中)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
25 1
|
18天前
|
算法 C语言 C++
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145(上)
从C语言到C++_25(树的十道OJ题)力扣:606+102+107+236+426+105+106+144+94+145
17 1
|
24天前
LeetCode——572—— 另一棵树的子树
LeetCode——572—— 另一棵树的子树
|
26天前
力扣337.打家劫舍3(树形dp)
力扣337.打家劫舍3(树形dp)