二叉树经典题题解

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

目录

🍅1.单值二叉树🍅

🍉 2.相同的树🍉

🍊3.对称二叉树🍊

🍎4.另一颗树的子树🍎

🍏5.翻转二叉树🍏

 🍑6.平衡二叉树🍑


二叉树经典题题解

二叉树经典题题解

🍅1.单值二叉树🍅

题目OJ链接  力扣

题目描述:

二叉树经典题题解

思路:

采用递归的思想,判断当前节点是否与左右孩子相等,不相等则返回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);
}

 🍉2.相同的树🍉

题目链接 力扣

题目描述:二叉树经典题题解

 思路:

利用递归的思想,先判断当前两个树根节点是否相同,然后再分别递归两个树当前节点的左孩子和右孩子进行比较,如果过程中有不相等的节点例如则返回false,或者一个树的节点存在而另一个树的节点不存在则返回false,直到递归到两个树的空节点说明之前的节点都相等则返回true

代码:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){
    if(p==NULL&&q==NULL)//递归到两个树的空节点则返回真
    return true;
    if(p==NULL||q==NULL)//一棵树的节点存在而另一颗的节点不存在则返回false
    return false;
    if(p->val!=q->val)//节点的值不相等则返回fasle
    return false;
    //分别递归两个树的左右子树,并将结果相与并返回
    return isSameTree(p->left,q->left)&&isSameTree(p->right,q->right);
}

🍊3.对称二叉树🍊

题目链接 力扣

题目描述:

二叉树经典题题解

 思路:

复用第二题相同的树的代码,相同的树题目中是将一颗树的根节点与另一颗的根节点比较,然后再分别比较左孩子和右孩子,这题我们可以将比较反过来,即一个树节点的左孩子和另一个数节点的右孩子进行比较,一个树节点的右孩子和另一个树节点的右孩子进行比较

代码:

 bool _isSymmetric(struct TreeNode* root1,struct TreeNode* root2)
 {
    if(root1==NULL&&root2==NULL)//递归到两个树的空节点则为真
    return true;
    if(root1==NULL||root2==NULL)//有一个树的节点存在而另一个树的节点不存在则返回false
    return false;
    if(root1->val!=root2->val)//节点的值不相等则返回false
    return false;
    //分别递归两个树的左右子树,左孩子节点与右孩子比较,右孩子节点与左孩子比较 
    return _isSymmetric(root1->left,root2->right)&&_isSymmetric(root1->right,root2->left);
 }
bool isSymmetric(struct TreeNode* root){
    return _isSymmetric(root->left,root->right);
}

🍎4.另一颗树的子树🍎

题目链接力扣

题目描述:

二叉树经典题题解

 思路:

利用递归的思想,判断两棵树是否都为空树,都为空树则返回真,再判断两颗子树是否有一个为空有一个不为空,如果是说明两个树不同则返回false。先判断整颗树是否与该子树相同,再递归判断左子树是否与该子树相同,最后判断递归右子树是否与该子树相同,如果左右子树都不与该子树,则返回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);
}
bool isSubtree(struct TreeNode* root, struct TreeNode* subRoot){
   if(root==NULL&&subRoot==NULL)//两个树都为空则返回真
    return true;
    if(root==NULL||subRoot==NULL)//两个树有一个为空有一个不为空则返回false
    return false;
    if(isSameTree(root,subRoot))//判断整个树是否与该子树相同
    return true;
    if(isSubtree(root->left,subRoot))//再判断左子树是否与该子树相同
    return true;
    if(isSubtree(root->right,subRoot))//最后判断左子树是否与该子树相同
    return true;
    //左右子树都不和该子树相同则返回false
    return false;
}

🍏5.翻转二叉树🍏

题目链接力扣

题目描述:二叉树经典题题解

 思路:

利用递归的思想,首先判断当前树是否为空树,为空树则返回空,接着进行翻转,首先将当前根节点的左右孩子进行交换,由于节点之间是进行指针链接的,故交换了左右孩子即交换了左右子树,然后递归交换左子树的左右孩子,最后递归交换右子树的左右孩子,直到递归到空节点则结束

代码:

void  _invertTree(struct TreeNode* root)
{
    if(root==NULL)//递归到空节点则结束
    return;
    //左右孩子进行交换
    struct TreeNode* tmp=root->left;
    root->left=root->right;
    root->right=tmp;
    递归左右子树
    _invertTree(root->left);
    _invertTree(root->right);
}
struct TreeNode* invertTree(struct TreeNode* root){
   if(root==NULL)
   return NULL;
    _invertTree(root);
    return root;
}

🍑 6.平衡二叉树🍑

题目链接力扣

题目描述:二叉树经典题题解

思路:

先写出求一棵树的高度的函数(见上一篇文章),再判断整棵树的左右子树高度差的绝对值是否小于1,如果左子树存在则递归左子树,判断左子树的左右子树高度差的绝对值是否小于1,然后如果右子树存在则递归左子树,判断右子树的左右子树高度差的绝对值是否小于1,如果左子树的左右子树高度差和右子树的左右子树高度差绝对值都小于1则返回真,或者直到递归到空节点或者叶子结点则说明之前的递归过程没有返回false即平衡二叉树的条件,此时返回true

代码: 

//求树的高度的函数
 int HeightTree(struct TreeNode* root)
 {
     if(root==NULL)
     return 0;
     if(root->left==NULL&&root->right==NULL)
     return 1;
     int left=HeightTree(root->left);
     int right=HeightTree(root->right);
     return left>right? left+1:right+1;
 }
bool isBalanced(struct TreeNode* root){
    if(root==NULL)//递归到空节点则返回真
    return true;
    if(root->left==NULL&&root->right==NULL)//递归到叶子节点则函数真
    return true;
    if(abs(HeightTree(root->left)-HeightTree(root->right))>1)//判断当前左右子树高度差绝对值
     return false;
    if(root->left)//左子树存在则递归左子树
    {
        if(isBalanced(root->left)==false)
        return false;
    }
    if(root->right)//右子树存在则递归右子树
    {
        if(isBalanced(root->right)==false)
        return false;
    }
    //左右子树的左右子树高度差绝对值都小于1则返回真
    return true;
}

好啦,关于二叉树经典题解我们就先学到这里,如果对您有所帮助,欢迎一键三连~文章来源地址https://www.toymoban.com/news/detail-421656.html

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

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

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

相关文章

  • 二叉树经典算法题目

    省略 输入一棵二叉树的根节点,求该树的深度。从根节点到叶节点依次经过的节点(含根、叶节点)形成树的一条路径,最长路径的长度为树的深度。 例如: 给定二叉树 [3,9,20,null,null,15,7] , 返回它的最大深度 3 。 思路:递归,当前数的深度等于左子数和右子树其中最大深

    2024年02月09日
    浏览(58)
  • 【C语言题解】 | 144. 二叉树的前序遍历

    提示: 树中节点数目在范围 [0, 100] 内 函数原型: 首先先观察一下这个函数原型, TreeNode* root 为形参,传入根节点, int* returnSize 为形参,在函数调用时用于返回改题目所求数组的长度,因为由于C语言的局限,只能返回一个参数,所以采用这种通过传入指针的形参,来改变

    2024年01月18日
    浏览(44)
  • 【数据结构】二叉树经典题目

    相信大部分人看了题目描述之后,都会和我一样一脸的懵逼。直到我看到了一个描述才恍然大悟 分为3种情况: 左右都为空 --省略 右为空,左不为空 – 省略 左为空,右不为空–不省略 这里复习一下二叉树的前序遍历、中序遍历、和后序遍历 前序的结果是:ABDEGCF 中序的结

    2024年02月10日
    浏览(54)
  • 数据结构与算法--二叉树与树(单选题含题解)

    1、对以下算法功能最准确的描述是()。 A.判断二叉树根结点值是否为e B.判断二叉树是否存在值为e结点 C.求二叉树中值为e结点的层次 D.求二叉树值为e的结点的个数 C 2、二叉树的形态 由 3 个结点可以构造出 ▁▁▁▁▁ 种不同形态的二叉树。 A.2 B.3 C.4 D.5 D 由n个结点可以构

    2024年02月03日
    浏览(41)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第一弹)

    朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 目录 前言: 一、 二、

    2024年02月10日
    浏览(40)
  • 数据结构:二叉树经典例题(单选题)-->你真的掌握二叉树了吗?(第二弹)

     朋友们、伙计们,我们又见面了,本期来给大家解读一下有关二叉树的经典例题,如果看完之后对你有一定的启发,那么请留下你的三连,祝大家心想事成! C 语 言 专 栏: C语言:从入门到精通 数据结构专栏: 数据结构 个  人  主  页 : stackY、 ​ 目录   前言: 一、

    2024年02月10日
    浏览(88)
  • Java LeetCode篇-深入了解二叉树的经典解法(多种方式实现:构造二叉树)

    🔥博客主页: 【 小扳_-CSDN博客】 ❤感谢大家点赞👍收藏⭐评论✍     文章目录         1.0 从前序与中序遍历序列来构造二叉树         1.1 实现从前序与中序遍历序列来构造二叉树思路            1.2 代码实现从前序与中序遍历序列来构造二叉树         2.0 从中序

    2024年02月05日
    浏览(77)
  • 力扣第236题——二叉树的最近公共祖先 (C语言题解)

    给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。 百度百科中最近公共祖先的定义为:“对于有根树 T 的两个节点 p、q,最近公共祖先表示为一个节点 x,满足 x 是 p、q 的祖先且 x 的深度尽可能大( 一个节点也可以是它自己的祖先 )。” 示例 1: 示例 2: 示例

    2024年01月20日
    浏览(41)
  • C语言经典算法之判断二叉树

    目录 前言 A.建议 B.简介 一 代码实现 二 时空复杂度 A.时间复杂度 B.空间复杂度 三 优缺点 A.优点: B.缺点: 四 现实中的应用 1.学习算法最重要的是理解算法的每一步,而不是记住算法。 2.建议读者学习算法的时候,自己手动一步一步地运行算法。 tips:文中的对数均以2为底

    2024年01月19日
    浏览(44)
  • 二叉树经典OJ题——【数据结构】

    W...Y的主页  😊 代码仓库分享 💕  今天我们来进行二叉树的OJ练习,就是利用二叉树的前序、中序、后续以及晨序遍历的特性进行OJ训练。话不多说,来看我们的第一道题。 【leetcode 965.单值二叉树】 OJ链接  如果二叉树每个节点都具有相同的值,那么该二叉树就是 单值 二

    2024年02月07日
    浏览(46)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包