👨🎓作者:bug菌 ✏️博客:CSDN、掘金等 💌公众号:猿圈奇妙屋 🚫特别声明:原创不易,转载请附上原文出处链接和本文声明,谢谢配合。 🙏版权声明:文章里可能部分文字或者图片来源于互联网或者百度百科,如有侵权请联系bug菌处理。
题目: 给你两棵二叉树的根节点
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
题目来源: LeetCode官网题目难度:⭐⭐
题意讲的很清楚,就是判断两颗二叉树是否完全相同,其实就可以梳理成以下三点:
这还不简单么。最暴力的解法就是递归。优化思路就上升到了深度优先或者广度优先搜索法。具体实现请看我如下操作:
具体算法代码实现如下:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
// 皆空,直接返回
if(p == null && q == null){
return true;
}
// 如果其中一棵树为空,另一棵不为空,则一定不相同
if((p == null && q != null) || (p != null && q == null)){
return false;
}
// 如果两棵树皆不为空,但是根节点的值不同,则一定不相同。
if(p.val !=q.val){
return false;
}
//排除以上特殊情况,只需要都为true则说明两树完全相同。
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right); }
}
具体算法代码实现如下:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
//两数都为空,直接返回
if (p == null && q == null) {
return true;
//存在一方为空,则不可能相同
} else if (p == null || q == null) {
return false;
} else if (p.val != q.val) {
return false;
} else {
return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
}
复杂度分析:
复杂度分析:
其实以上两种思路本质上都差不多的,唯独就是解题思路方向上细致不太一样。都是是运用递归思想,连枚举方式都是一样的,先枚举排除特殊性,然后再递归对比左右子数是否相等。
再者,解题道路千万条,欢迎小伙伴们脑洞大开,如果你们有啥更好的想法或者思路,欢迎评论区告诉我哦,大家一起互相借鉴互相学习,方能成长的更快。
好啦,以上就是本期的所有内容啦,咱们下期见咯。