【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

简介: 【数据结构】单值二叉树 & 相同的树 & 翻转二叉树(五)

一,单值二叉树

题目详情:

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树

只有给定的树是单值二叉树时返回 true;否则返回 false;

提示:

1,给定树的结点树范围是【1,100】

2,每个结点的值都是整数,范围为【0,99】

示例1:

输入:nums = [1,1,1,1,1,NULL,1 ]

输出:true

示例2:

输入:nums = [2,2,2,5,2]

输出:false

解法:父子比较法

解题思路:

以上图为例:要判断根结点为(2)的二叉树是否为单值二叉树可以分解为(2)的左右子树是否为单值二叉树,这就很符合递归思路可以用递归解决;【(2)= 左子树 && 右子树】

判断条件:

当结点为NULL时返回 true

当子结点存在时,并且与父亲结点的值不相同时返回 false;

思路实现:

首先要判空:

//判断空
if(root==NULL)
{
    return true;
}

当结点为空时不影响父亲孩子之间的关系;

然后判断孩子,父亲之间的值的关系:

//判断孩子与父亲的值
if(root->left && root->val!=root->left->val)
{
    return false;
}
if(root->right && root->val!=root->right->val)
{
    return false;
}

判断孩子,父亲所对应的值是否相同;

大事化小:以上条件都满足时,还需左右子树是否为单值二叉树,只有当左右子树都为单值二叉树时才为 true;

//化为两颗子树是否为单值树
return isUnivalTree(root->left) && isUnivalTree(root->right);

要用逻辑与,需要双方为真时才返回 true;

源代码:

bool isUnivalTree(struct TreeNode* root){
    //判断空
    if(root==NULL)
    {
        return true;
    }
    //判断孩子与父亲的值
    if(root->left && root->val!=root->left->val)
    {
        return false;
    }
    if(root->right && root->val!=root->right->val)
    {
        return false;
    }
    //化为两颗子树是否为单值树
    return isUnivalTree(root->left) && isUnivalTree(root->right);
}

我们可以用示例来演算一遍,流程也是这样的;

像这种递归题目要演算其过程需要画图,这样才是最直观的;

二,相同的树

题目详情:

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

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

提示:

两棵树上的结点数目都在范围【0,100】内

-104<=Node.val<=10

示例1:

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

输出:true

示例2:

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

输出:false

示例3:

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

输出:false

解法:比较法

解题思路:

要判断两棵树是否一致,要考虑的是他们的结点是否都存在,结点对应的值是否相同;

以上图为例:根结点相同了,还要判断其左右子树是否也相同,然后层层往下,这道题也是用递归思想;

思路实现:

首先要判断他们的结点是否对应存在:

    //双方都为空
    if(p==NULL && q==NULL)
    {
      return true;
    }
    //一方为空另一方不为空
    if((p==NULL || q==NULL) 
    {
      return false;
    }

当双方对应的结点都为空时返回 true

当双方对应的结点只有一方为空,另一方不为空时,返回 false

然后判断它们对应的结点的值的情况:

    //判断所对应的值是否相同
    if(p->val != q->val)
    {
      return false;
    }

当所对应的值不相等则返回 false;

大事化小:当以上条件都满足时,还需要判断这两棵树所对应的左右子树是否相同;

    //判断其对应的左右子树是否也相同
    return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);

源代码:

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

这就是判断两颗二叉树是否相同问题的解题思路了,还是利用递归;

三,翻转二叉树

题目详情:

给你一棵二叉树的根节点 root ,翻转这棵二叉树,并返回其根节点

示例1:

输入:root = [ 4,2,7,1,3,6,9 ]

输出:[ 4 7 2 9 6 3 1 ]

示例2:

输入:root = [ 2,1,3 ]

输出:[ 2,3,1]

示例3:

输入:root = [ ]

输出:[ ]

解法:替换法

解题思路:

翻转翻转所谓翻转其实就是将左右子树换个位置而已,直接将其交换,层层交换下去直至NULL,用递归来实现;

思路实现:

首先还是判空,如果为空直接返回NULL即可;

然后直接交换左,右子树,再让其左,右子树也如此下去,就完成了对整颗树的翻转了,在返回根结点即可;

源代码:

void swap(struct TreeNode** left,struct TreeNode** right)
{
    struct TreeNode* tmp=*left;
    *left=*right;
    *right=tmp;
}
struct TreeNode* invertTree(struct TreeNode* root){
    //判空
    if(root==NULL)
    {
        return NULL;
    }
    //交换
    swap(&root->left,&root->right);
    //左子树翻转
    invertTree(root->left);
    //右子树翻转
    invertTree(root->right);
    return root;
}

基本上与二叉树相关的练习都要使用递归思想前期培养递归思路最好就是画图解析,这个很重要,画图能让我们更直观的感受结点之间的关系,特别是感受那个返回的过程领悟其中的奥妙,久而久之我们对于递归的思路就更加清晰了,不至于摸不着北;

第五阶段就到这里了,这阶段带大家刷道些题目来感受一下二叉树的魅力!

后面博主会陆续更新;

如有不足之处欢迎来补充交流!

完结。。

目录
相关文章
|
26天前
|
存储 算法
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
【数据结构和算法】--- 二叉树(4)--二叉树链式结构的实现(2)
16 0
|
26天前
|
存储 算法 Linux
【数据结构和算法】---二叉树(1)--树概念及结构
【数据结构和算法】---二叉树(1)--树概念及结构
17 0
|
2天前
|
存储
【数据结构】树和二叉树的概念及结构
数据结构——树和二叉树的概念及结构
16 3
【数据结构】树和二叉树的概念及结构
|
1天前
|
存储 算法 Python
Python数据结构新视角:Trie树与Suffix Tree的相爱相杀,你站哪边?
【7月更文挑战第20天】在编程领域,Trie树(前缀树)与Suffix Tree(后缀树)犹如双星,各有专长。Trie树高效检索字符串集合,擅长前缀匹配,适用于自动补全和拼写检查;Suffix Tree则管理字符串所有后缀,加速子串查询,解最长公共前缀和重复子串难题。两者在不同场景发光发热,Trie树于快速响应的自动完成胜出,Suffix Tree则在基因序列分析和文本模式识别中独领风骚。抉择之间,应用场景与需求成关键,恰如剑客选剑,唯理解本质方能制胜。
|
26天前
【数据结构】判断二叉树是否是完全二叉树
【数据结构】判断二叉树是否是完全二叉树
17 5
|
26天前
【数据结构】链式二叉树的层序遍历
【数据结构】链式二叉树的层序遍历
22 5
|
26天前
|
存储 测试技术
【数据结构】手把手分析:链式二叉树的实现
【数据结构】手把手分析:链式二叉树的实现
20 5
|
2天前
|
存储 数据处理 开发者
告别繁琐查找!Python高级数据结构Trie树与Suffix Tree,让数据处理更轻松!
【7月更文挑战第19天】Python的Trie树优化字符串搜索,利用前缀减少无效操作,提升效率;Suffix Tree则高效处理后缀问题,尤其适用于文本搜索与生物信息学。虽构建复杂,但能加速后缀查询。掌握这两种数据结构,能有效应对大规模数据挑战,简化处理流程,提升开发效率。
|
26天前
|
算法 分布式数据库
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
【数据结构和算法】--- 二叉树(5)--二叉树OJ题
15 1
|
27天前
|
算法
【C/数据结构与算法】:二叉树经典OJ
【C/数据结构与算法】:二叉树经典OJ
17 0
【C/数据结构与算法】:二叉树经典OJ