【LeetCode】——链式二叉树经典OJ题详解

这篇具有很好参考价值的文章主要介绍了【LeetCode】——链式二叉树经典OJ题详解。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

 =========================================================================

主页点击直达:个人主页

我的小仓库:代码仓库

C语言偷着笑:C语言专栏

数据结构挨打小记:初阶数据结构专栏

Linux被操作记:Linux专栏

LeetCode刷题掉发记:LeetCode刷题

算法头疼记:算法专栏 

=========================================================================

目录

前言:

LeetCode 965.单值二叉树

LeetCode 100.相同的树

LeetCode 101.对称二叉树

LeetCode 144 145 94 .二叉树的前、中、后序遍历

LeetCode 572.另一棵树的子树


前言:

在之前的文章讲解了二叉树的链式结构的实现以及前、中、后序的遍历。不知道大家看完后有没有理解和有所收获,今天基于那篇文章给大家分享讲解几道经典的题目,更便于大家的理解和深入。

二叉树的题目一定要会两个思想

第一个思想:拆分 一定要将二叉树拆分为根、左子树、右子树首先就是要判断根结点是否为空。第二个思想:递归,善于使用递归。


LeetCode 965.单值二叉树

OJ链接

题目描述: 

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

示例 1:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

示例 2:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

审题总结:

判断一个二叉树这所有节点的值是否相等,相等返回true,否则返回false;

思路讲解:首先判断根是否为空,如果为空直接返回true。不为空判断左子树是否存在,存在的话判断和根节点的值是否相等,如果相等返回true,否则返回false;继续判断右子树是否存在,存在的话判断和根节点的值是否相等,如果相等返回true,否则返回法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);
}

LeetCode 100.相同的树


OJ链接

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

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

示例 1:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

示例 2:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

示例 3:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

思路讲解:

先将根拆结点拆分出来,两个根节点有三种情况,都为空、两个根节点中有一个为空。如果都为空,则返回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);
}

LeetCode 101.对称二叉树


OJ链接

题目描述:

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

示例 1:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

示例 2:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

输入:root = [1,2,2,null,3,null,3]
输出:falses

思路讲解:

这个题目和上个题目非常的相似,还是拆分为根、左子树、右子树。这里将两个子树看成单独的树,就和上面题的思路大差不差了。不同的是要判断左边的值和右边的值是否相等,这样才算对称。

实现代码

 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->right)
    &&isSameTree(p->right,q->left);
    
 }
bool isSymmetric(struct TreeNode* root){
 if(root!=NULL)
 {
     return isSameTree(root->left,root->right);
 }
 else
 return true;
}

LeetCode 144 145 94 .二叉树的前、中、后序遍历

前序遍历OJ链接

中序遍历OJ链接

后序遍历OJ链接

关于二叉树的前、中、后序遍历的文章点击直达,这里我不做介绍。由于这三个题目是差不多只是将遍历的值用数组的形式便是出来,所以我就只讲解前序遍历、中、后序遍历交给大家练习。

题目描述:给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 

示例 1:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

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

示例 2:

输入:root = []
输出:[]

示例 3:

输入:root = [1]
输出:[1]

思路讲解:

首先求出这棵二叉树有几个结点,根据结点动态开辟相应大小的空间。将根节点、动态开辟的数组,变量的地址,交给一个前序遍历的函数,根据前序遍历的规则,进行递归给数组赋值。

实现代码

 int treesize(struct TreeNode*root)
 {
     return root==NULL? 0:treesize(root->left)+treesize(root->right)+1;
 }
 void preoder(struct TreeNode *root,int *a,int *pi)
 {
     if(root==NULL)
     return;
     a[(*pi)++]=root->val;
     preoder(root->left,a,pi);
     preoder(root->right,a,pi);
 }
int* preorderTraversal(struct TreeNode* root, int* returnSize){
     int n=treesize(root);
     int *a=(int *)malloc(sizeof(int )*n);
     int j=0;
    preoder(root,a,&j);
    *returnSize=n;
     return a;
}

LeetCode 572.另一棵树的子树

OJ链接

题目描述:

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

示例 1:

【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

输入:root = [3,4,5,1,2], subRoot = [4,1,2]
输出:true

示例 2:【LeetCode】——链式二叉树经典OJ题详解,算法,数据结构挨打小记,leetcode,算法

输入:root = [3,4,5,1,2,null,null,null,null,0], subRoot = [4,1,2]
输出:falses

思路讲解:

这个题和上面的LeetCode 100.相同的树基本上也大差不差。首先判断根节点是否为空,如果根节点为空,则直接返回false;不为空则直接使用是否为相同的树判断函数,判断所给树是否为子树,如果为真则直接返回true,使用递归遍历根节点的左右子树和所给所给子树相比较。

实现代码

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

bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
if(root==NULL)
{
    return false;
}
if(root->val==subRoot->val)
{
    if(isSameTree(root,subRoot))
    return true;
}
return isSubtree(root->left,subRoot)||isSubtree(root->right,subRoot);

}

 今天的分享就到此结束了,希望大家阅读完可以有所收获,同时也感谢各位看官的三连支持。文章有问题可以直接留言,我一定及时认真的修改。文章来源地址https://www.toymoban.com/news/detail-714693.html

到了这里,关于【LeetCode】——链式二叉树经典OJ题详解的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】【数据结构】二叉树必刷OJ题

    👀 樊梓慕: 个人主页   🎥 个人专栏: 《C语言》《数据结构》《蓝桥杯试题》《LeetCode刷题笔记》《实训项目》 🌝 每一个不曾起舞的日子,都是对生命的辜负 目录 前言 【LeetCode】226.翻转二叉树 【LeetCode】100.相同的树 【LeetCode】5.对称二叉树 【LeetCode】9.另一颗树的子树

    2024年02月08日
    浏览(51)
  • 【数据结构】二叉树的链式结构的实现 -- 详解

    在学习二叉树的基本操作前,需先要创建一棵二叉树,然后才能学习其相关的基本操作。为了降低大家学习成本,此处手动快速创建一棵简单的二叉树,快速进入二叉树操作学习。 注意 :上述代码并不是创建二叉树的方式。 学习二叉树结构,最简单的方式就是遍历。所谓

    2024年02月12日
    浏览(43)
  • 数据结构与算法—二叉树数组表示(ArrayBinTree)、二叉树的链式表示(LinkedBinTree)的基于C++模板代码实现

    1、二叉树的顺序表示:ArrayBinTree.h 二叉树的顺序表示法操作方便,但缺点是容易造成存储空间浪费。 这是一个用数组实现的二叉树类模板。它可以创建一个空树,也可以在指定的位置插入结点并设置结点的值,可以删除子树,并支持逐层遍历。使用该类时,需要提供一个元

    2024年02月06日
    浏览(44)
  • 链式二叉树OJ题思路分享

    ⏩博主CSDN主页:杭电码农-NEO⏩   ⏩专栏分类:刷题分享⏪   ⏩代码仓库:NEO的学习日记⏩   🌹关注我🫵带你刷更多C语言和数据结构的题!   🔝🔝 链式二叉树这一个板块的考题还是比较多的,这里我给大家分享几道很经典的OJ题,仅供参考! 分别是 1. 单值二叉树 力扣965题--

    2024年02月06日
    浏览(32)
  • 【数据结构】二叉树(链式)

    😛作者:日出等日落 📘 专栏:数据结构           抱怨是一件最没意义的事情。如果实在难以忍受周围的环境,那就暗自努力练好本领,然后跳出那个圈子。 目录  🎄二叉树 ✔二叉树的结构:  ✔BuyNode(创建二叉树节点): 🎄基本函数操作: ✔PreOrder(前序递归遍历):

    2024年02月01日
    浏览(46)
  • 【数据结构】二叉树——链式结构

    目录  一、前置声明 二、二叉树的遍历 2.1 前序、中序以及后序遍历 2.2 层序遍历 三、节点个数以及高度 3.1 节点个数 3.2 叶子节点个数 3.3 第k层节点个数 3.4 二叉树的高度/深度 3.5 查找值为x的节点 四、二叉树的创建和销毁 4.1 构建二叉树 4.2 二叉树销毁 4.3 判断二叉树

    2024年02月16日
    浏览(47)
  • 数据结构与算法之二叉树: Leetcode 111. 二叉树的最小深度 (Typescript版)

    二叉树的最小深度 https://leetcode.cn/problems/minimum-depth-of-binary-tree/ 描述 就 给定一个二叉树,找出其最小深度。 最小深度是从根节点到最近叶子节点的最短路径上的节点数量。 说明:叶子节点是指没有子节点的节点。 示例 1 示例 2 提示 树中节点数的范围在 [0, 1 0 5 10^5 1 0 5 ] 内

    2024年02月06日
    浏览(44)
  • 【算法与数据结构】654、LeetCode最大二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :【算法与数据结构】106、LeetCode从中序与后序遍历序列构造二叉树这两道题有些类似,相关代码可以互相参考,本题明示了要用递归来做,那么递归三要素不可缺少: 输入参数和返

    2024年02月09日
    浏览(46)
  • 【算法与数据结构】226、LeetCode翻转二叉树

    所有的LeetCode题解索引,可以看这篇文章——【算法和数据结构】LeetCode题解。    思路分析 :这道题的思路很简单,本质上就是遍历每一个节点,然后交换左右节点。我们可以用前中后遍历或者是层次遍历法来做,参考这两篇文章,【算法与数据结构】144、94、145LeetCode二

    2024年02月16日
    浏览(41)
  • 【数据结构】二叉树链式结构

    🚀write in front🚀 📜所属专栏:初阶数据结构 🛰️博客主页:睿睿的博客主页 🛰️代码仓库:🎉VS2022_C语言仓库 🎡您的点赞、关注、收藏、评论,是对我最大的激励和支持!!! 关注我,关注我,关注我 , 你们将会看到更多的优质内容!!   在之前的二叉树的顺序结

    2024年02月03日
    浏览(41)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包