目录一、题目描述二、解题思路题目难度:简单 一、题目描述 给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。 如果两个树在结构上相同,并且节点具有相同的值,则
题目难度:简单
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
LeetCode链接:相同的树
核心思路:
先比较两颗二叉树的根节点
递归过程演示:
依次比较两颗二叉树中「当前树(1、2、3、4、5、6)的根节点」是否相等,这样每个节点都被比较了一次。
bool isSameTree(struct Treenode* p, struct TreeNode* q){
// 1. 先比较两颗树的根节点
// 都为空,返回true,说明满足相同的树的条件
if(p == NULL && q == NULL)
{
return true;
}
// 一个为空一个不为空,返回false
if(p == NULL || q == NULL)
{
return false;
}
// 都不为空,但节点值不相等,返回false
if(p->val != q->val)
{
return false;
}
// 2. 经过前面的if的判断,既然运行到这里了,说明当前节点相等
// 则继续比较左子树和右子树的根节点
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
时间复杂度:假设两棵树都有 n 个节点,最多比较 n 次,所以为 O ( N ) O(N) O(N)
空间复杂度:往下递归会开辟栈帧空间,函数返回时会还给操作系统,所以「空间复杂度」和「递归的最大深度」有关,最坏情况下,「递归的最大深度」就是有 n 的节点二叉树的最大深度,所以为 O ( N ) O(N) O(N)
到此这篇关于C语言详解判断相同树案例分析的文章就介绍到这了,更多相关C语言判断相同树内容请搜索编程网以前的文章或继续浏览下面的相关文章希望大家以后多多支持编程网!
--结束END--
本文标题: C语言详解判断相同树案例分析
本文链接: https://www.lsjlt.com/news/147055.html(转载时请注明来源链接)
有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341
下载Word文档到电脑,方便收藏和打印~
2024-03-01
2024-03-01
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
2024-02-29
回答
回答
回答
回答
回答
回答
回答
回答
回答
回答
0