【数据结构与算法】二叉树基础OJ -- 上 (巩固提高)-1

简介: 【数据结构与算法】二叉树基础OJ -- 上 (巩固提高)-1

leetcode 965.单值二叉树

题目来源:965. 单值二叉树 - 力扣(LeetCode)


题目描述:

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。
只有给定的树是单值二叉树时,才返回 true;否则返回 false。

示例 :

43fc542aa9b5487e8b7ab3f1f952b83f.png



解题思路:

   

a == b b == c  推论: a == c,利用了值的传递性,根与子树也是可以利用这一性质解题。
        1.开始的时候先判断这棵树是否为空,假设是空,那么直接返回true,因为NULL也可以是这棵树唯一的一个值。
     
         2.接着若根节点不为空,那么这时候先访问根的左子树root->left,让其作为if的判断条件(判断左子树是否为空),然后用&&连接起另一个判断条件:root->left->val != root->val 也就是访问左子树的val与其根节点的val是否不相等,
        这里着重说明一下:root->val 如果等于root->left->val是说明不了问题的,因为相等了还是要找下一个节点判断与其根节点什么关系,这属于是不确定的条件,
        所以要找确定的条件:直接让root->left->val != root->val,如果条件成立则直接返回false.
右子树同理.
     
        3.如果根节点与子树相等,那么就直接让isUnivalTree(root->left) && isUnivalTree(root->right)作为返回条件.
        用&&的原因就是有其中一棵子树值不全相等,那么说明该树不是单值,返回false

图解:

5983eba7548442dbb7cdafcdfff4cac8.png



代码实现:


bool isUnivalTree(struct TreeNode* root){
    if(root == NULL)
        return true;
   
    if(root->left && root->left->val != root->val)
        return false;
    if(root->right && root->right->val != root->val)
        return false;
    return isUnivalTree(root->left)&&isUnivalTree(root->right);
}

执行:


fdd3f169cb31415c9b8ccb87ed47bc0e.png


leetcode 100.相同的树

题目来源:100. 相同的树 - 力扣(LeetCode)


题目描述:

给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。


示例:

4d76116437f74e379d98ed476b9bd2ea.png



解题思路:

首先检查两棵树是否都为空。如果是,则它们具有相同的值,返回true。
如果两棵树中有一棵为空而另一棵不为空,则它们不相等,返回false。
如果两棵树的当前节点的值不相等,则它们不相等,返回false。
如果以上情况都不满足,即两棵树的当前节点的值相等,则递归地调用isSameTree函数,传入左子树,并进行相同的比较。
同样地,递归地调用isSameTree函数,传入右子树,并进行相同的比较。
如果左右子树的比较结果都为true,则说明两棵树相等,返回true;否则返回false
图解:图上数字代表遍历顺序,说明两子树是同时进行的。




代码实现:


bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    //找确定的条件
    //两树皆为空时,它们具有相同的值 
    if(p == NULL && q == NULL)
        return true;
    //当两树一个节点为空,另一个不为空
    if(p == NULL || q == NULL)
        return false;
    //都不为空,但是不相等,
    if(p->val !=q->val)
        return false;
   
    //假设两树第一个节点相等,则递归函数,反复上述过程
    return isSameTree(p->left,q->left) 
    && isSameTree(p->right,q->right);
}


执行:



e8268d0f99e34820ad3fa3e767c8f9ef.png

leetcode 101.对称二叉树

题目来源:101. 对称二叉树 - 力扣(LeetCode)


题目描述:

给你一个二叉树的根节点 root , 检查它是否轴对称。

ddf3722ac2ba43cf8f29ff65b53de865.png

示例:




解题思路:

        首先,因为oj里面的原函数满足不了我们在一颗树内同时操作左右子树的需求,因为只有一个指针,操作不了左右两个方向。(记住原函数包括函数名、返回条件、参数都是不能改变的)


a7040644358d4a13b0a778d0c53105be.png


       这时候我们定义一个函数is_Symmetrict(root->left,root->right),接着传入指针,然后可以同时开始操作,左右子树。


       1.先判断左右子树是否为空,因为地址为空在结构上也是对称的一个结果,然后返回true


       2. 判断以下子树一个为空,另一个是否也为空,两者同时为空则返回false,


       3、两子树不为空但不相等,返回false。


       若上述条件均不满足,即左子树和右子树都不为空,且它们的根节点的值相等,那么继续递归地调用 is_Symmetrict 函数,分别传入左子树的左子树和右子树的右子树,以及左子树的右子树和右子树的左子树。


       如果递归调用的返回值都为 true,则说明左子树和右子树对称,返回 true;否则返回 false


图解:

843b5a02474c430ea0b6609ca256965b.png

代码实现:


bool is_Symmetrict(struct TreeNode*leftroot,struct TreeNode*rightroot)
{
    //找确定的条件
    //左子树右子树两个为空
    if(leftroot==NULL && rightroot == NULL)
        return true;
    //左子树或右子树,一个为空
    if(leftroot == NULL || rightroot == NULL)
        return false;
    if(leftroot->val != rightroot->val)
    return false;
    return is_Symmetrict(leftroot->left , rightroot->right) && 
    is_Symmetrict(leftroot->right , rightroot->left);
}
bool isSymmetric(struct TreeNode* root){
   return is_Symmetrict(root->left,root->right);   
}


执行:



bb2e8f70cefd4e3e8c27f3dbe684bfe0.png


【数据结构与算法】二叉树基础OJ -- 上 (巩固提高)-2

https://developer.aliyun.com/article/1456941

相关文章
|
17天前
|
算法
分享一些提高二叉树遍历算法效率的代码示例
这只是简单的示例代码,实际应用中可能还需要根据具体需求进行更多的优化和处理。你可以根据自己的需求对代码进行修改和扩展。
|
21天前
|
存储 缓存 算法
如何提高二叉树遍历算法的效率?
选择合适的遍历算法,如按层次遍历树时使用广度优先搜索(BFS),中序遍历二叉搜索树以获得有序序列。优化数据结构,如使用线索二叉树减少空指针判断,自定义节点类增加辅助信息。利用递归与非递归的特点,避免栈溢出问题。多线程并行遍历提高速度,注意线程安全。缓存中间结果,避免重复计算。预先计算并存储信息,提高遍历效率。综合运用这些方法,提高二叉树遍历算法的效率。
45 5
|
25天前
|
C语言
【数据结构】二叉树(c语言)(附源码)
本文介绍了如何使用链式结构实现二叉树的基本功能,包括前序、中序、后序和层序遍历,统计节点个数和树的高度,查找节点,判断是否为完全二叉树,以及销毁二叉树。通过手动创建一棵二叉树,详细讲解了每个功能的实现方法和代码示例,帮助读者深入理解递归和数据结构的应用。
82 8
|
24天前
|
机器学习/深度学习 JSON 算法
二叉树遍历算法的应用场景有哪些?
【10月更文挑战第29天】二叉树遍历算法作为一种基础而重要的算法,在许多领域都有着不可或缺的应用,它为解决各种复杂的问题提供了有效的手段和思路。随着计算机科学的不断发展,二叉树遍历算法也在不断地被优化和扩展,以适应新的应用场景和需求。
26 0
|
2月前
|
存储 算法 关系型数据库
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
这篇文章主要介绍了多路查找树的基本概念,包括二叉树的局限性、多叉树的优化、B树及其变体(如2-3树、B+树、B*树)的特点和应用,旨在帮助读者理解这些数据结构在文件系统和数据库系统中的重要性和效率。
24 0
数据结构与算法学习二一:多路查找树、二叉树与B树、2-3树、B+树、B*树。(本章为了解基本知识即可,不做代码学习)
|
2月前
|
存储 算法 搜索推荐
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
这篇文章主要介绍了顺序存储二叉树和线索化二叉树的概念、特点、实现方式以及应用场景。
27 0
数据结构与算法学习十七:顺序储存二叉树、线索化二叉树
|
2月前
|
存储 算法
探索数据结构:分支的世界之二叉树与堆
探索数据结构:分支的世界之二叉树与堆
|
2月前
|
存储 人工智能 算法
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
这篇文章详细介绍了Dijkstra和Floyd算法,这两种算法分别用于解决单源和多源最短路径问题,并且提供了Java语言的实现代码。
83 3
数据结构与算法细节篇之最短路径问题:Dijkstra和Floyd算法详细描述,java语言实现。
|
2月前
|
机器学习/深度学习 存储 缓存
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
文章主要介绍了排序算法的分类、时间复杂度的概念和计算方法,以及常见的时间复杂度级别,并简单提及了空间复杂度。
33 1
数据结构与算法学习十:排序算法介绍、时间频度、时间复杂度、常用时间复杂度介绍
|
2月前
|
搜索推荐 算法
数据结构与算法学习十四:常用排序算法总结和对比
关于常用排序算法的总结和对比,包括稳定性、内排序、外排序、时间复杂度和空间复杂度等术语的解释。
22 0
数据结构与算法学习十四:常用排序算法总结和对比