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

 

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

🌈个人主页:主页链接

🌈算法专栏:专栏链接

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

🌈LeetCode专栏:专栏链接 

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

🌈代码仓库:Gitee链接

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

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

目录

题目:100. 相同的树

题解:

代码实现:

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

题解:

代码实现:

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

题解:

代码实现:

完结撒花:


题目:100. 相同的树

题解:

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

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

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

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

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

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

 

代码实现:


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. 另一棵树的子树

题解:

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

我们可以把问题拆分为:这颗树的子树与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. 二叉树的最近公共祖先

题解:

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

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

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

 若只有一边找到了,则说明这其中一个节点可能做为另一个节点的根,则直接返回根节点(left,right)即可

之后再加入递归的元素,依次遍历访问每棵树的左节点称为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专题Ⅲ】已经结束。

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

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

🌈诸君,山顶见!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.mfbz.cn/a/7243.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

MySQL基础-变量/流程控制/游标/触发器

文章目录MySQL基础-变量/流程控制/游标/触发器一、变量1、系统变量2、用户变量二、流程控制1、分支语句2、循环语句3、跳转语句三、游标1、概念2、使用四、触发器1、触发器概念2、触发器使用3、触发器的优缺点MySQL基础-变量/流程控制/游标/触发器 一、变量 在MySQL数据库的存…

RocketMQ水平扩展及负载均衡详解

文章目录 Broker端水平扩展Broker负载均衡commit logProducer负载均衡Consumer负载均衡集群模式广播模式RocketMQ是一个分布式具有高度可扩展性的消息中间件。本文旨在探索在broker端,生产端,以及消费端是如何做到横向扩展以及负载均衡的。 Broker端水平扩展 Broker负载均衡…

前端项目-05-轮播图banner和Floor组件开发-全局轮播图组件抽取

目录 1-轮播图模块数据开发 2-floor组件开发 3-抽取全局轮播图组件 1-轮播图模块数据开发 轮播图需要用到swiper插件&#xff0c;先安装5.4.5版本的swiper&#xff1a;npm install --save swiper^5.4.5 --force 模拟从服务器获取数据&#xff1b; 1-编写mockRequests的js…

【ACWing算法课】二分查找

前言&#x1f349; 二分查找一个简单的算法&#xff0c;但是因为边界问题往往写不好。特此记录模板&#xff0c;以便快捷使用。 [二分查找]从列表q找到第一个>k的数&#xff0c;返回位置&#x1f451; [二分查找]从列表q找到第一个>k的数&#xff0c;返回位置def bsear…

three.js实现3d球体树状结构布局——树状结构的实现

目录系列文章安装依赖基本分析实体类场景相机渲染器辅助线环境光点光源球形几何体球形几何体的材质线几何体线几何体的材质物体文本轨道控制实现效果实现源码参考文档系列文章 three.js实现3d球体树状结构布局——添加入场、出场、点击放大等动画 安装依赖 npm i three three…

Adaptive AUTOSAR——Time Synchronization(VRTE 3.0 R21-11)

15 Time Synchronization 15.1 What is Time Synchronization? 时间同步是自适应平台基础中的一个功能集群。时间同步通过库向应用程序提供C API&#xff0c;该库作为RTA-VRTE入门套件的一部分提供&#xff0c;并与应用程序链接以访问该功能。 本版本包含非常少量的时间同步…

ASIC-WORLD Verilog(1)一日Verilog

写在前面 在自己准备写一些简单的verilog教程之前&#xff0c;参考了许多资料----asic-world网站的这套verilog教程即是其一。这套教程写得极好&#xff0c;奈何没有中文&#xff0c;在下只好斗胆翻译过来&#xff08;加了自己的理解&#xff09;分享给大家。 这是网站原文&…

Helm学习笔记

文章目录概念定义helm组件helm的工作流程helm安装helm仓库helm部署应用helm应用的更新或回退或卸载概念 定义 学习helm首先得了解helm是什么&#xff0c;我们先来看一下helm的定义&#xff1a;helm是将kubernetes的各种资源对象打包&#xff0c;类似于Linux中的yum工具&#…

【HTML系列】第六章 · 框架标签、HTML实体、HTML全局属性和meta元信息

写在前面 Hello大家好&#xff0c; 我是【麟-小白】&#xff0c;一位软件工程专业的学生&#xff0c;喜好计算机知识。希望大家能够一起学习进步呀&#xff01;本人是一名在读大学生&#xff0c;专业水平有限&#xff0c;如发现错误或不足之处&#xff0c;请多多指正&#xff0…

【前端面试题——微信小程序】

目录1.请谈谈wxml与标准的html的异同&#xff1f;2.请谈谈WXSS和CSS的异同&#xff1f;3.请谈谈微信小程序主要目录和文件的作用&#xff1f;4.请谈谈小程序的双向绑定和vue的异同&#xff1f;5.简单描述下微信小程序的相关文件类型&#xff1f;6.微信小程序有哪些传值(传递数据…

jsp+javaEE+mysql校园物品租赁系统dzkf5294程序

1&#xff0e;物品信息管理&#xff1a;管理员发布物品信息后&#xff0c;普通用户便可以查询到该物品信息&#xff0c;用户选择某个物品信息&#xff0c;查询物品信息&#xff0c;管理员审核添加&#xff0c;或删除物品信息。 2&#xff0e;租赁管理&#xff1a;管理员发布租赁…

ChatGPT大解密:带您探讨机器学习背后的秘密、利用与发展

一、什么是机器学习&#xff1f;二、ChatGPT 的运作原理三、ChatGPT 生活利用1、自然语言处理2、翻译3、自动回复四、ChatGPT vs 其他相关技术五、ChatGPT 的未来1、未来发展2、职业取代3、客服人员4、翻译人员5、语言学家6、机遇与挑战六、结语这篇文章&#xff0c;将带着各位…

ThreeJS-投影、投影模糊(十七)

无投影&#xff1a; 完整的代码&#xff1a; <template> <div id"three_div"></div> </template> <script> import * as THREE from "three"; import { OrbitControls } from "three/examples/jsm/controls/Or…

再不转型为ChatGPT程序员,有遭受降维打击的危险

Open AI在演示GPT-4的时候&#xff0c;有这么一个场景&#xff1a;给一个界面草图&#xff0c;就可以生成网页代码。这个演示非常简单&#xff0c;如果界面原型比较复杂呢&#xff1f;像这样&#xff1a;ChatGPT能不能直接生成HTML, CSS,JavaScript代码&#xff0c;把这个网页给…

MongoDB副本集Command failed with error 10107 (NotMaster):on server

问题 通过DataGrip连接的MongoDB节点&#xff0c;之前可以新增或更新数据。某天突然不能新增或更新数据&#xff0c;报错信息如下&#xff1a; 具体的报错信息&#xff1a; Command failed with error 10107 (NotMaster): not master on server 10.19.21.11:30386. The full…

HNU-电路与电子学-实验3

实验三 模型机组合部件的实现&#xff08;二&#xff09;&#xff08;实验报告格式案例&#xff09; 班级 计XXXXX 姓名 wolf 学号 2021080XXXXX 一、实验目的 1&#xff0e;了解简易模型机的内部结构和工作原理。 2&#xff0e;分析模型机的功能&am…

【Linux】LVM与磁盘配额

文章目录1.LVM1.1 LVM概述1.2 LVM机制1.3 LVM管理命令1.4 LVM应用实例2. 磁盘配额2.1 磁盘配额概述2.2 磁盘配额管理2.3 启用磁盘配额支持2.4 磁盘配额应用实例1.LVM 1.1 LVM概述 Logical Volume Manager&#xff0c;逻辑卷管理 ● 能够在保持现有数据不变的情况下动态调整磁盘…

43掌握自动化运维工具 Puppet 的基本用法,包括模块编写、资源管理

Puppet是一种自动化配置管理工具&#xff0c;可以自动化地部署、配置和管理大规模服务器环境。本教程将介绍Puppet的基本用法&#xff0c;包括模块编写和资源管理。 模块编写 在Puppet中&#xff0c;模块是一组相关的类、文件和资源的集合。模块可以用于部署和配置应用程序、服…

图形编辑器:排列移动功能的实现

大家好&#xff0c;我是前端西瓜哥。这次来实现一下图形编辑器排列&#xff08;arrange&#xff09;功能的实现。 先看效果。 有四种移动方式&#xff1a; 置顶&#xff08;Front&#xff09;&#xff1a;将指定的图形移动到顶部&#xff1b;置底&#xff08;Back&#xff09…

嵌入式学深度学习:1、Pytorch框架搭建

嵌入式学深度学习&#xff1a;1、Pytorch框架搭建1、介绍2、Pytorch开发环境搭建2.1、查看GPU是否支持CUDA2.2、安装Miniconda2.3、使用Conda安装pytorch2.4、安装常用库3、简单使用验证1、介绍 深度学习是机器学习的一种&#xff0c;如下图&#xff1a; 目前深度学习应用场景…
最新文章