ACM 选手图解 LeetCode 相同的树

简介: ACM 选手图解 LeetCode 相同的树

大家好呀,我是帅蛋。


今天解决相同的树,这是一道检验两棵二叉树是否相同的题目。


你如果看过我上篇关于【对称二叉树】的讲解,你就会发现在某种程度上这两道题可以看作是一道题。


那为什么我还要写这道题呢?

640.jpg


对,我就是要看看小婊贝儿们到底有没有学会。


640.png


   LeetCode 100:相同的树



题意


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


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


示例


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

输出:true

640.png



提示


  • 两棵树上的节点数目都在范围 [0,100] 内。
  • -10^4 <= Node.val <= 10^4


   题目解析



难度简单,似曾相识。


如果你已经看过【对称二叉树】这篇文章,那你看到这道题的时候,应该就已经知道怎么做了。


如果你没看过,那建议回过头儿去看一下,看完了,做这道题的感觉也就来了。

640.jpg

我在【对称二叉树】中说过,对称二叉树就是看左右子树是否互相翻转,和根节点没什么关系。


既然没什么关系,那把根节点拿掉,其实就是在比较两棵树。

640.png


那你看,从这个角度来看,这两道题其实就是一种类型的题,再直白点,就是一道题。


只不过稍微有点区别的是,对称二叉树是下面这种比较方式:


  • 左子树的左子树和右子树的右子树比较。
  • 左子树的右子树和右子树的左子树比较。

640.png


而本题相同的树则是下面这种比较方式:


  • p 树的根节点和 q 树的根节点比较。
  • p 树的左子树和 q 树的左子树比较。
  • p 树的右子树和 q 树的右子树比较。

640.png


是不是就很一目了然?

640.jpg

递归法


都是老套路。

640.jpg


根据【递归算法】文章中讲的,实现递归,需要两步:


  • 找出重复的子问题(递推公式)。
  • 终止条件。


(1) 找出重复的子问题。


这个在上面看图的时候其实已经找出来了。


p 树的左子树和 q 树的左子树,p 树的右子树和 q 树的右子树是否相等


如果相等就返回 true,不相等就返回 false。



         

(2) 确定终止条件。


同样,相同的树这道题因为比较的是节点的值是否相同,所以涉及的情况有点多。


首先是节点为空的情况(空树),根节点为空,分为 3 种情况:

  • p,q 的根节点都为空,即为空树,显然两棵树相同。
  • p 的根节点为空,q 的根节点不为空,显然两棵树不相同。
  • p 的根节点不为空,q 的根节点为空,显然也是不相同的。


根节点为空的情况判断完了,剩下就是节点不为空的情况,根节点不为空,其实终止就 1 种情况:


  • 比较 p,q 根节点的值,如果不相等,则两棵树不相同。

Python 代码实现


         



Java 代码实现



         


假设 p 树有 n 个节点,q 树有 m 个节点。


此解法,不管是 p 和 q 树是否相同,都会将节点少的树的每个节点遍历一遍,所以时间复杂度为 O(min(n,m))


使用递归,在过程中额外调用了栈空间,所以空间复杂度为 O(min(n,m))


非递归法(迭代)


这道题其实就是对于每一层来说,只要 p 树和 q 树的对应节点存在且相等即可


其实这还是类似于层次遍历,使用队列来解决


每次将 p 树和 q 树对应层的节点依次入队列,比如 p 的左节点和 q 的左节点入队列,p 的右节点和 q 的右节点入队列。


比如对于下图

640.png


首先初始化队列,并将 p 树和 q 树的根节点入队列。

640.png


         

当队列不为空,将前两个元素出队列进行比较。

640.png


         


试下面再依次将 p 的左孩子和 q 的左孩子,p 的右孩子和 q 的右孩子入队列。


640.png



接下来还是按照上面的方式出队列、比较、入队列...直至队列为空。


Python 代码实现


         


Java 代码实现



         



同样,非递归法,时间复杂度为 O(min(n,m)),空间复杂度为 O(min(n,m))



图解相同的树到这就结束辣,你写对了么?


通过这道题,我其实想说,很多时候你会发现,题目不过是在某类解决办法方面做加法减法


希望大家能多多思考,做题的时候不要做完了就算了。


当然文章也不能看完就算了呀,记得帮我点赞 + 在看 + 转发呀,么么哒。


我是帅蛋,我们下次见!

相关文章
|
7天前
|
SQL 算法 数据可视化
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
LeetCode题目99:图解中叙遍历、Morris遍历实现恢复二叉树搜索树【python】
|
7天前
|
存储 SQL 算法
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
LeetCode题目100:递归、迭代、dfs使用栈多种算法图解相同的树
|
7天前
|
存储 算法 数据可视化
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
python多种算法对比图解实现 验证二叉树搜索树【力扣98】
|
12天前
|
搜索推荐 Java
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
单源最短路(只有一个起点)bfs,多源BFS,目录力扣675.为高尔夫比赛砍树,多源最短路问题:力扣542.01矩阵力扣1020.飞地的数量
|
12天前
|
算法 Java Go
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
【经典算法】LeetCode 100. 相同的树(Java/C/Python3/Go实现含注释说明,Easy)
5 0
|
20天前
|
算法 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
|
20天前
|
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
|
20天前
|
算法 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
|
25天前
LeetCode——572—— 另一棵树的子树
LeetCode——572—— 另一棵树的子树
|
26天前
LeetCode———100——相同的树
LeetCode———100——相同的树