(C语言版)力扣(LeetCode)+牛客网(nowcoder)二叉树基础oj练习

news/2024/4/19 2:01:29

在这里插入图片描述

二叉树基础oj练习

  • 965. 单值二叉树
    • 题目
    • 解法
  • 100. 相同的树
    • 题目
    • 解法
  • 101. 对称二叉树
    • 题目
    • 解法
  • 144. 二叉树的前序遍历
    • 题目
    • 解法
  • 94. 二叉树的中序遍历
    • 题目
    • 解法
  • 145. 二叉树的后序遍历
    • 题目
    • 解法
  • 572. 另一棵树的子树
    • 题目
    • 解法
  • KY11 二叉树遍历
    • 题目
    • 解法
  • 结语

965. 单值二叉树

题目

如果二叉树每个节点都具有相同的值,那么该二叉树就是单值二叉树。

只有给定的树是单值二叉树时,才返回 true;否则返回 false。

题目链接:单值二叉树

解法

代码如下:

bool isUnivalTree(struct TreeNode* root){if(!root)return true;if(root->left){if(root->val!=root->left->val||!isUnivalTree(root->left))return false;}if(root->right){if(root->val!=root->right->val||!isUnivalTree(root->right))return false;}return true;
}

首先判定二叉树是否为空,如果为空,直接返回true即可
再判定左右子树是否等值,不等返回false
嵌套递归下一层左右子树
遍历完都没进入条件语句,说明都相等,返回true

100. 相同的树

题目

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

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

题目链接:相同的树

解法

代码如下:

bool isSameTree(struct TreeNode* p, struct TreeNode* q){if(p==NULL&&q==NULL)return true;else if(p==NULL||q==NULL)return false;else if(p->val!=q->val)return false;else return(isSameTree(p->left,q->left)&&isSameTree(p->right,q->right));}

首先判定两树是否均为空,如果都为空,则返回true
有一个不为空则返回false
都不为空再比较值,不等则返回false
再向下递归遍历左右子树即可。

101. 对称二叉树

题目

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

题目链接:对称二叉树

解法

代码如下:

bool ret(struct TreeNode* p,struct TreeNode* q)
{if(!p&&!q)return true;else if(!p||!q)return false;else if(p->val!=q->val)return false;elsereturn ret(p->left,q->right)&&ret(p->right,q->left);
}
bool isSymmetric(struct TreeNode* root){return ret(root,root);
}

这里还是使用递归的写法,由于这个算法需要两个参数实现,所以我们再写一个ret函数来实现,最后返回ret函数返回值即可

和上一题类似,如果树为空,则返回true,后面递归遍历时,是左右对称点比较
第二个条件也是为了后期递归时判断左右对称点是否一个为空,则返回false
第三个条件同理,判断值是否不等,不等则返回false
最后递归左右对称点,遍历整个二叉树。

144. 二叉树的前序遍历

题目

给你二叉树的根节点 root ,返回它节点值的 前序 遍历。

题目链接:二叉树的前序遍历

解法

代码如下:

void _preorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;ret[(*returnSize)++]=root->val;_preorder(root->left,ret,returnSize);_preorder(root->right,ret,returnSize);
} 
int* preorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_preorder(root,ret,returnSize);return ret;
}

首先我们开辟一个数组空间,题目要求是[0,100],我这里是直接给了200,将returnSize初始化为0
再调用子函数,子函数首先判定结点为空直接不返回值
下面的三个就是关键了
前序遍历是按照二叉树根左右的顺序,所以
先将根节点的值放入数组,在递归遍历左子树,再递归遍历右子树
最后返回数组,结果即为二叉树的前序遍历。

94. 二叉树的中序遍历

题目

给定一个二叉树的根节点 root ,返回 它的 中序 遍历 。

题目链接:二叉树的中序遍历

解法

代码如下:

void _inorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;_inorder(root->left,ret,returnSize);ret[(*returnSize)++]=root->val;_inorder(root->right,ret,returnSize);
} 
int* inorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_inorder(root,ret,returnSize);return ret;
}

和上面的题目思路是一样的,只不过中序遍历顺序为左根右
所以我们将子函数稍微调整,先遍历左子树,再记录根节点,最后遍历右子树

145. 二叉树的后序遍历

题目

给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

题目链接:二叉树的后序遍历

解法

代码如下:

void _posorder(struct TreeNode*root,int* ret,int* returnSize)
{if(root==NULL)return;_posorder(root->left,ret,returnSize);_posorder(root->right,ret,returnSize);ret[(*returnSize)++]=root->val;} 
int* postorderTraversal(struct TreeNode* root, int* returnSize){int* ret=malloc(sizeof(int)*200);*returnSize=0;_posorder(root,ret,returnSize);return ret;
}

和上面的题目思路还是一样的,只不过后序遍历顺序为左右根
所以我们将子函数稍微调整,先遍历左子树,再遍历右子树,最后记录根节点

572. 另一棵树的子树

题目

给你两棵二叉树 root 和 subRoot 。检验 root 中是否包含和 subRoot 具有相同结构和节点值的子树。如果存在,返回 true ;否则,返回 false 。

二叉树 tree 的一棵子树包括 tree 的某个节点和这个节点的所有后代节点。tree 也可以看做它自身的一棵子树。

题目链接:另一棵树的子树

解法

代码如下:

bool check(struct TreeNode* o, struct TreeNode* t)
{if (!o && !t) return true;if ((o && !t) || (!o && t) || (o->val != t->val)) return false;return check(o->left, t->left) && check(o->right, t->right);
}bool isSubtree(struct TreeNode* o, struct TreeNode* t)
{if (!o) return false;return check(o, t) || isSubtree(o->left, t) || isSubtree(o->right, t);
}

首先我们判定如果树为空直接返回false
再看下面的返回第一个条件
主树和子树如果都为空则返回true,只有一个为空或则值不相等则返回false
再比较主树的左子树和子树的左子树以及主树的右子树和子树的右子树
遍历完如果相同则为true,如果不同则向左子树再与子树比较,左子树不同再与右子树比较
都不同最后就返回false

KY11 二叉树遍历

题目

编一个程序,读入用户输入的一串先序遍历字符串,根据此字符串建立一个二叉树(以指针方式存储)。 例如如下的先序遍历字符串: ABC##DE#G##F### 其中“#”表示的是空格,空格字符代表空树。建立起此二叉树以后,再对二叉树进行中序遍历,输出遍历结果。

题目链接:二叉树遍历

解法

代码如下:

#include <stdio.h>
typedef struct TreeNode
{int* val;struct TreeNode* left;struct TreeNode* right;
}TreeNode;
TreeNode* creatTree(char* s,int* count)
{if(s[*count]=='#'||s[*count]=='\0')return NULL;TreeNode* newtree = malloc(sizeof(TreeNode));newtree->val=s[(*count)++];newtree->left=creatTree(s,count);(*count)++;newtree->right=creatTree(s,count);return newtree;
}
void inorder(TreeNode* root)
{if(root==NULL)return;inorder(root->left);printf("%c ",root->val);inorder(root->right);}
int main() {char s[200];scanf("%s",&s);int count=0;TreeNode* root=creatTree(s,&count);inorder(root);return 0;
}

首先是二叉树结构体的建立
包含值val和左右子树节点
然后是建二叉树,分别有输入值的字符串数组和初始化下标0两个参数
如果该元素为#或者\0则直接返回空即可
上述条件语句不执行则创建节点,根据二叉树前序遍历的顺序,先输入根的值,再遍历左子树,最后遍历右子树
然后是中序输出函数,节点为空,直接返回,
不执行上述条件语句,则按中序输出顺序,先遍历左子树节点,再输出根节点,最后遍历右子树节点
再看主函数
根据题意不超过100个字符,这里我直接给了200空间
然后就是输入字符串,初始化count为0,为了记录下标
最后调用建树和中序输出两个函数即可

结语

这里的解法代码部分来自力扣官方和作者自己的解法,作者只是进行了详细的剖析和部分改动方便大家理解和提升自己,学会多角度观察问题,解决问题。

有兴趣的小伙伴可以关注作者,如果觉得内容不错,请给个一键三连吧,蟹蟹你哟!!!
制作不易,如有不正之处敬请指出
感谢大家的来访,UU们的观看是我坚持下去的动力
在时间的催化剂下,让我们彼此都成为更优秀的人吧!!!
在这里插入图片描述


http://www.ppmy.cn/news/73339.html

相关文章

springboot+java超市收银管理系统idea

考虑到实际生活中在超市 POS 收银管理方面的需要以及对该系统认真的分析&#xff0c;将系统权限按管理员和员工这两类涉及用户划分。 Spring Boot 是 Spring 家族中的一个全新的框架&#xff0c;它用来简化Spring应用程序的创建和开发过程。也可以说 Spring Boot 能简化我们之…

UML类图画法及其关系

UML类图画法及其关系 本文主要是介绍 UML类图画法及其关系&#xff0c;方便今后温习&#xff01;&#xff01;&#xff01; 一、类之间的关系汇总 泛化&#xff08;Generalization&#xff09;实现&#xff08;Realization&#xff09;关联&#xff08;Association&#xff…

Linux 学习笔记(七):时间片

一、时间片概念 时间片&#xff08;timeslice&#xff09;又称为 “量子”&#xff08;quantum&#xff09;或 “处理器片”&#xff08;processor slice&#xff09;&#xff0c;是分时操作系统分配给每个正在运行的进程微观上的一段 CPU 时间&#xff08;在抢占内核中是&…

将有序数组转换为二叉树

md这个破CSDN模板怎么没了&#xff0c;编辑器也死难用&#xff0c;气死 1、题目 给你一个整数数组 nums &#xff0c;其中元素已经按 升序 排列&#xff0c;请你将其转换为一棵 高度平衡 二叉搜索树。 高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不…

异地研发团队都使用哪些研发协同工具?盘点7类最主流的研发管理协同软件

产品研发场景下好用的协同办公软件有哪些&#xff1f;分享7类研发过程中主流的协同办公软件&#xff0c;比如项目管理协作与问题跟踪工具PingCode、代码托管与版本控制平台github、持续集成与持续部署&#xff08;CI/CD&#xff09;工具jinkens、文档协作与知识管理工具conflue…

Node开发Web后台服务

简介 Node.js 是一个基于Google Chrome V8 引擎的 JavaScript 运行环境。Node.js 使用了一个事件驱动、非阻塞式 I/O 的模型&#xff0c;使其轻量又高效。Node.js 的包管理器 npm&#xff0c;是全球最大的开源库生态系统。 能方便地搭建响应速度快、易于扩展的网络应用&#…

支付宝沙箱支付(java电脑版)

目录 下载支付demo配置环境AlipayConfig 下载支付demo 网址&#xff1a;https://open.alipay.com/ 下载并打开项目发现无法运行&#xff1a; 手动转化项目&#xff1a; 等待下载整理一下maven pom 通过tomat部署运行测试。 导入阿里支付的pom依赖 <dependency> &l…

《计算机网络—自顶向下方法》 Wireshark实验(十):NAT 协议分析

NAT&#xff08;Network Address Translation&#xff09;网络地址转换&#xff0c;即在私有地址和全局地址之间转换的协议。私有地址是不能用在 Internet 上(路由器将丢弃寻址这种地址的包)的内部地址。这些地址是不能够在公网上面用的&#xff0c;只能用在局域网的内部。私有…

可以白嫖的语音识别开源项目whisper的搭建详细过程 | 如何在Linux中搭建OpenAI开源的语音识别项目Whisper

原文来自我个人的博客。 1、前提条件 服务器为GPU服务器。点击这里跳转到我使用的GPU服务器。我搭建 whisper 选用的是 NVIDIA A 100显卡&#xff0c;4GB显存。 Python版本要在3.8~3.11之间。 输入下面命令查看使用的Python版本。 python3 -V2、安装Anaconda 为啥要安装A…

教材管理系统

目 录 第一章 引言 3 1.1 背景 3 1.1.1教材管理系统 3 1.1.2信息管理系统 3 1.2开发教材管理系统的目的和原则 5 1.3开发环境介绍 6 1.3.1 开发平台 6 1.3.2 数据库查询语言——SQL 8 1.3.3 数据库设计工具——ACCESS数据库管理系统 9 第二章 系统设计 11 2.1 系统分析 11 2.2 …

惯性导航论文详解:神经惯性定位

来源&#xff1a;投稿 作者&#xff1a;小灰灰 编辑&#xff1a;学姐 论文标题&#xff1a;Neural Inertial Localization 论文链接: https://arxiv.org/pdf/2203.15851v1.pdf 图1.从IMU测量到位置估计。给定惯性传感器数据&#xff08;左&#xff09;&#xff0c;我们的方法…

面了一个测试工程师要求月薪26K,总感觉他背了很多面试题...

最近有朋友去华为面试&#xff0c;面试前后进行了20天左右&#xff0c;包含4轮电话面试、1轮笔试、1轮主管视频面试、1轮hr视频面试。 据他所说&#xff0c;80%的人都会栽在第一轮面试&#xff0c;要不是他面试前做足准备&#xff0c;估计都坚持不完后面几轮面试。 其实&…

测试类的使用

1.在pom文件中添加依赖 <dependencies> <dependency><groupId>junit</groupId><artifactId>junit</artifactId><version>4.12</version><scope>compile</scope> </dependency> </dependencies>2.在s…

Vmware Linux磁盘空间扩容

Linux磁盘空间扩容 VMware虚拟机中配置&#xff08;1&#xff09;进入虚拟机设置界面&#xff0c;选择扩展磁盘容量。&#xff08;2&#xff09; 本次是在原来30G的基础上扩展为50G。 Linux中设置&#xff08;1&#xff09; 可以看出sda3是根分区&#xff0c;下面按照博客提示&…

掌握XPath:安装配置、解析流程、语法和实战练习全攻略

目录 引言 xpath安装与使用 解析流程与使用 xpath语法 xpath实战练习 引言 众所周知&#xff0c;XPath是Web开发中重要的工具之一&#xff0c;可以帮助我们在HTML或XML文档中快速定位和选择内容。但是对于初学者来说&#xff0c;XPath的安装配置、语法解析以及实际应用可…

响应式编程中Mono和Flux的区别

前言 当我们在使用Project Reactor&#xff0c;或者使用依赖于它的框架的时候。例如spring webflux&#xff0c;spring cloud gateway等&#xff0c;经常会用看到代码中有Mono和Flux两个术语。 响应式流 Reactor是由Pivotal公司开发的开源框架&#xff0c;它是开发响应式应用…

魔改车钥匙实现远程控车:(番外)在macOS上安装使用MicroPython

前言 哈哈&#xff0c;各位可能会奇怪为啥上一篇文章还在说怎么在 ESP32C3 上安装 Arduino&#xff0c;现在怎么又变成了安装 MIcroPython。 其实是因为上次写 Arduino 还是我高中时候的事了&#xff0c;已经不太会了。 虽然 MIcroPython 我从来没有接触过&#xff0c;但是 …

织梦网做城市分站织梦分站群二级目录织梦城市分站教程

一、安装网站 1、上传到服务器上输入www.xxxx.com/install进行安装(具体安装方法找百度一大堆); 可以参考http://www.hlzcb.com/zhimengxueyuan/zhimenganzhuangshiyong/25830.html 2.安装好后台点击后台系统→数据库备份还原→数据还原,点击下面的开始还原数据; 二、设…

vue导出word

先在项目中安装所需要的依赖包 npm install file-saver npm install docxtemplater-image-module-free npm install docxtemplater npm install pizzip npm install jszip-utils //angular-expressions 如果需要自定义图片尺寸需要安装此依赖包如图&#xff0c;一定要装完整 …

关于SD webui 部署运行的一些坑

[Bug 1]: RuntimeError: Couldnt install gfpgan 可以先尝试&#xff1a; pip install gfpgan 不过是在虚拟环境venv下的 E:\stable-diffusion-webui\venv\Scripts\python.exe -m pip install gfpgan 如果还是无法安装gfpgan的原因是网络问题&#xff0c;就算已经科学上网…