【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

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

 【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

Halo,这里是Ppeua。平时主要更新C语言,C++,数据结构算法......感兴趣就关注我吧!你定不会失望。

🌈个人主页:主页链接

🌈算法专栏:专栏链接

     我会一直往里填充内容哒!

🌈LeetCode专栏:专栏链接 

    目前在刷初级算法的LeetBook 。若每日一题当中有力所能及的题目,也会当天做完发出

🌈代码仓库:Gitee链接

🌈点击关注=收获更多优质内容🌈

 呜呜呜呜 今天被蓝桥杯爆杀了

目录

题目:100. 相同的树

题解:

代码实现:

题目:572. 另一棵树的子树

题解:

代码实现:

题目:236. 二叉树的最近公共祖先

题解:

代码实现:

完结撒花:


【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

题目:100. 相同的树

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

题解:

这题算是简单题,我们依然从最简单的情况来考虑。

如果只有一个节点的时候:怎么判断这两个节点是否相等呢?

首先,先判断其左右根的属性是否相同.

属性的含义是:其是否都有左右根,若没有,则没有是否没有同一边

其次再进行判断,这个点的值是否相等.

这样就完成了对一个节点的判断,我们只需要一一比较这两棵树的节点是否相同,就能比较出来了

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

 

代码实现:


struct TreeNode {
     int val;
     struct TreeNode *left;
      struct TreeNode *right;
 };


#include<iostream>
using namespace std;
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));

}   

题目:572. 另一棵树的子树

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

题解:

这题与上面那题大同小异,寻找一棵树的子树,

我们可以把问题拆分为:这颗树的子树与subroot是否相等,这样就又变成了,上面那个问题.

如何判断两棵树是否相等.(只是多了一个遍历每颗子树的过程)

废话不多说,我们直接来看代码吧

代码实现:

#include<iostream>
using namespace std;
struct TreeNode {
     int val;
     struct TreeNode *left;
     struct TreeNode *right;
};
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
    if(!p&&!q)return true;
    if(!p||!q)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(isSameTree(root, subRoot))return true;
    return isSubtree(root->left,subRoot)||isSubtree(root->right, subRoot);
}

题目:236. 二叉树的最近公共祖先

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

题解:

依旧先看看基础情况,若访问的这个节点与p或者q相同,则说明找到了他,则直接返回就可以了.

之后再判断是否两边都找到了

若两边都找到了,则说明left与right最近的公共节点就是当前访问的这个节点root.

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ 若只有一边找到了,则说明这其中一个节点可能做为另一个节点的根,则直接返回根节点(left,right)即可

【树】你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ

之后再加入递归的元素,依次遍历访问每棵树的左节点称为left

                        ​​​​​​​        ​​​​​​​     依次遍历访问每棵树的右节点称为right

若出现以上三种情况.则不为空. 

代码实现:

#include<iostream>
using namespace std;
struct TreeNode {
      int val;
      TreeNode *left;
      TreeNode *right;
 };
 
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(root==NULL||root->val==p->val||root->val==q->val)return root;
        TreeNode* left=lowestCommonAncestor(root->left,  p, q);
        TreeNode*right=lowestCommonAncestor(root->right,p,q);
        if(left!=NULL&&right!=NULL)return root;
        if(right==NULL)return left;
        if(left==NULL)return right;
        return NULL;
    }
};

完结撒花:

🌈本篇博客的内容【你真的会二叉树了嘛? --二叉树LeetCode专题Ⅲ】已经结束。

🌈若对你有些许帮助,可以点赞、关注、评论支持下博主,你的支持将是我前进路上最大的动力。

🌈若以上内容有任何问题,欢迎在评论区指出。若对以上内容有任何不解,都可私信评论询问。

🌈诸君,山顶见!文章来源地址https://www.toymoban.com/news/detail-419096.html

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

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

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

相关文章

  • 【数据结构刷题专题】—— 二叉树

    二叉树 二叉树刷题框架 二叉树的定义: 1 二叉树的遍历方式 【1】前序遍历 【2】后序遍历 【3】中序遍历 【4】层序遍历 2 二叉树的属性 【1】101. 对称二叉树 【2】104. 二叉树的最大深度 迭代法: 递归法: 【3】111.二叉树的最小深度 递归法: 迭代法: 【4】222. 完全二叉树的

    2024年04月10日
    浏览(42)
  • 【算法专题】二叉树中的深搜(DFS)

    深度优先遍历(DFS,全称为 Depth First Traversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分支,直到一条路径上的所有节点都被遍历完毕,然后再回溯到上一层,继续找⼀条路遍历。 在二叉树中,常见的深度优先遍历为

    2024年02月03日
    浏览(42)
  • 专题二:二叉树的深搜【递归、搜索、回溯】

    深度优先遍历 (DFS,全称为DepthFirstTraversal),是我们树或者图这样的数据结构中常用的⼀种遍历算法。这个算法会尽可能深的搜索树或者图的分⽀,直到⼀条路径上的所有节点都被遍历完毕,然后再回溯到上⼀层,继续找⼀条路遍历。 在⼆叉树中,常⻅的深度优先遍历为:

    2024年02月07日
    浏览(40)
  • Golang每日一练(leetDay0049) 二叉树专题(9)

    目录 144. 二叉树的前序遍历 Binary-tree Preorder Traversal  🌟 145. 二叉树的前序遍历 Binary-tree Postorder Traversal  🌟 对比: 94. 二叉树的中序遍历 Binary-tree Inorder Traversal  🌟 146. LRU缓存 LRU Cache  🌟🌟 🌟 每日一练刷题专栏 🌟 Golang每日一练 专栏 Python每日一练 专栏 C/C++每日一

    2024年02月04日
    浏览(42)
  • 【深度优先】【广度优先】Leetcode 104 二叉树的最大深度 Leetcode 111 二叉树的最小深度 Leetcode 110 平衡二叉树

    二叉树节点的深度: 指从根节点到该节点的最长简单路径边的条数或者节点数 (取决于深度从0开始还是从1开始) 二叉树节点的高度: 指从该节点到叶子节点的最长简单路径边的条数后者节点数 (取决于高度从0开始还是从1开始) 【前序求的是深度,后序求的是高度】 -

    2024年02月19日
    浏览(52)
  • 每天一道算法练习题--Day15 && 第一章 --算法专题 --- -----------二叉树的遍历

    二叉树作为一个基础的数据结构,遍历算法作为一个基础的算法,两者结合当然是经典的组合了。很多题目都会有 ta 的身影,有直接问二叉树的遍历的,有间接问的。比如要你找到树中满足条件的节点,就是间接考察树的遍历,因为你要找到树中满足条件的点,就需要进行遍

    2024年02月01日
    浏览(48)
  • 二叉树OJ题:LeetCode--965.单值二叉树

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

    2024年02月12日
    浏览(48)
  • 二叉树OJ题:LeetCode--101.对称二叉树

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

    2024年02月13日
    浏览(49)
  • 二叉树OJ题:LeetCode--226.翻转二叉树

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

    2024年02月11日
    浏览(44)
  • 二叉树OJ题:LeetCode--104.二叉树的最大深度

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

    2024年02月11日
    浏览(83)

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

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

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

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

二维码1

领取红包

二维码2

领红包