☆打卡算法☆LeetCode 100、相同的树 算法解析
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定两颗二叉树的根节点,编写函数来检验这两棵树是否相同。”题目链接:来源:力扣(LeetCode)链接:100. 相同的树 - ...
推荐阅读
大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。
一、题目
1、算法题目
“给定两颗二叉树的根节点,编写函数来检验这两棵树是否相同。”
题目链接:
来源:力扣(LeetCode)
链接:100. 相同的树 - 力扣(LeetCode) (leetcode-cn.com)
2、题目描述
给你两棵二叉树的根节点 p
和 q
,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入: p = [1,2,3], q = [1,2,3]
输出: true
示例 2:
输入: p = [1,2], q = [1,null,2]
输出: false
二、解题
1、思路分析
判断两个二叉树是否相同,需要这两个二叉树的结构完全相同且对应的节点的值也相同才返回true,所以,可以通过搜索的方式判断两个二叉树是否先沟通。
在搜索的时候会碰到四种情况:
- 两个二叉树都为空,则两个二叉树相同。
- 两个二叉树其中一个为空,则两个二叉树一定不相同。
- 两个二叉树都不为空,根节点的值以及子树的节点值都相同,则两个二叉树相同。
- 两个二叉树都不为空,根节点的值不同或者子树的节点值不相同,则两个二叉树不相同。
2、代码实现
代码参考:
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
if (p == null) return q == null;
return q != null && p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
}
}
3、时间复杂度
时间复杂度 : O(min(m,n))
其中m和n分别是两个二叉树的节点数,对两个二叉树同事进行搜索,只有当两个二叉树中的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉树的节点数。
空间复杂度: O(min(m,n))
其中m和n分别是两个二叉树的节点数,空间复杂度取决于递归调用的层数,递归调用的层数不会超过二叉树的最大高度。
三、总结
深度优先遍历算法,需要确定遍历的终止条件和返回值。
- 两个二叉树都为空,则两个二叉树相同,返回true。
- 两个二叉树其中一个为空,则两个二叉树一定不相同,返回false。
- 两个二叉树都不为空,根节点的值以及子树的节点值都相同,则两个二叉树相同,返回true。
- 两个二叉树都不为空,根节点的值不同或者子树的节点值不相同,则两个二叉树不相同,返回false。
当满足终止条件时进行返回。
【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)