☆打卡算法☆LeetCode 100、相同的树 算法解析

举报
恬静的小魔龙 发表于 2022/03/02 09:18:27 2022/03/02
【摘要】 推荐阅读CSDN主页GitHub开源地址Unity3D插件分享简书地址我的个人博客QQ群:1040082875大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。 一、题目 1、算法题目“给定两颗二叉树的根节点,编写函数来检验这两棵树是否相同。”题目链接:来源:力扣(LeetCode)链接:100. 相同的树 - ...

推荐阅读

大家好,我是小魔龙,Unity3D软件工程师,VR、AR,虚拟仿真方向,不定时更新软件开发技巧,生活感悟,觉得有用记得一键三连哦。

一、题目

1、算法题目

“给定两颗二叉树的根节点,编写函数来检验这两棵树是否相同。”

题目链接:

来源:力扣(LeetCode)

链接:100. 相同的树 - 力扣(LeetCode) (leetcode-cn.com)

2、题目描述

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

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

image.png

示例 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);
    }
}

image.png

3、时间复杂度

时间复杂度 : O(min(m,n))

其中m和n分别是两个二叉树的节点数,对两个二叉树同事进行搜索,只有当两个二叉树中的对应节点都不为空时才会访问到该节点,因此被访问到的节点数不会超过较小的二叉树的节点数。

空间复杂度: O(min(m,n))

其中m和n分别是两个二叉树的节点数,空间复杂度取决于递归调用的层数,递归调用的层数不会超过二叉树的最大高度。

三、总结

深度优先遍历算法,需要确定遍历的终止条件和返回值。

  • 两个二叉树都为空,则两个二叉树相同,返回true。
  • 两个二叉树其中一个为空,则两个二叉树一定不相同,返回false。
  • 两个二叉树都不为空,根节点的值以及子树的节点值都相同,则两个二叉树相同,返回true。
  • 两个二叉树都不为空,根节点的值不同或者子树的节点值不相同,则两个二叉树不相同,返回false。

当满足终止条件时进行返回。

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区)、文章链接、文章作者等基本信息, 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。