刚学完二叉树,来试试这些oj题练练手吧!-Toy模板网

这篇具有很好参考价值的文章主要介绍了刚学完二叉树,来试试这些oj题练练手吧!。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

🎈个人主页:🎈 :✨✨✨初阶牛✨✨✨
🐻推荐专栏1: 🍔🍟🌯C语言初阶
🐻推荐专栏2: 🍔🍟🌯C语言进阶
🔑个人信条: 🌵知行合一
🍉本篇简介:>:记录力扣的一些有关二叉树的入门题目.分享解题经验.
c语言实现:单值二叉树,相同的树,对称二叉树
金句分享:
✨总不能一生碌碌无为,还安慰自己平凡可贵吧.✨

前言

二叉树主要就是玩递归,相信大家学完二叉树以后,对递归有了更加深层的理解,可以试着做几道oj题,练一下手.

一、单值二叉树

声明:
题目来源于–力扣
题目链接: 传送门

题目描述:

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

示例1:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：[1,1,1,1,1,null,1]
输出：true

示例2:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：[2,2,2,5,2]
输出：false

解题思路:

递归结束条件,遇到NULL返回true
判断根节点的值与左子树的值是否相等.
不相等返回false
判断根节点的值与右子树的值是否相等.
不相等返回false
返回递归遍历这颗树的逻辑值.

代码实现:

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

提交记录:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

二、相同的树

声明:
题目来源于–力扣
题目链接: 传送门

题目介绍:

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

如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
相同返回:true
不同返回:false

示例1:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：p = [1,2,3], q = [1,2,3]
输出：true

示例2:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：p = [1,2], q = [1,null,2]
输出：false

解题思路

先考虑两棵树其中一棵为NULl的情况,返回false
(注意不是指一整颗树为NULl,而是指一方节点).
例如:
示例2中,第一颗树的左子树是值为2的结点,但是第二棵树的左子树是NULL.
两棵树都为NULL,返回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);
}

提交记录:
刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

三、对称二叉树

声明:
题目来源于–力扣
题目链接:

题目介绍:

给你一个二叉树的根节点 root ，检查它是否轴对称。
对称:返回true.
不对称:返回false

刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：root = [1,2,2,3,4,4,3]
输出：true

刚学完二叉树,来试试这些oj题练练手吧!,刷题集,数据结构,算法,c语言

输入：root = [1,2,2,null,3,null,3]
输出：false

解题思路:

难点在于,对称二叉树是需要遍历到左子树之后,回到根节点,去与右子树比较,为了实现这一要求,我们可以另写一个函数,直接将这棵树用两个root访问.从最开始的根节点开始,将这颗二叉树切割为二叉树 .

创建一个子函数check.参数为(struct TreeNode* root1,struct TreeNode* root2)
先判断这两颗树的根节点是否为NULL.为空则直接返回true.
一方为NULl时:返回false.
判断root1的值和root2的值是否相等.
root1递归时先访问其左子树,root2递归时先访问其右子树.
root1递归后访问右子树,root2递归后访问左子树.
返回递归结果的逻辑值.

代码实现

bool check(struct TreeNode* root1,struct TreeNode* root2)
{
    if(root1==NULL&&root2==NULL)
       return true;
    //上面已经判断了都为NULL时的情况,则此时判断如果一方为空
    if(root1==NULL||root2==NULL)
        return false;
    if(root1->val!=root2->val)
        return false;
       //注意这里的递归顺序,重点
    return check(root1->left,root2->right)&& check(root1->right,root2->left);
}
bool isSymmetric(struct TreeNode* root){
   return check(root,root);
}