数据结构基础8:二叉树oj+层序遍历。
二叉树oj+层序遍历
- 题目一:二叉树的销毁:
- 方法一:前序遍历:
- 方法二:后序遍历:
- 题目二:二叉树查找值为x的节点
- 方法一:
- 方法二:
- 方法三:
- 题目三:层序遍历:
- 方法一:
- 题目四:相同的树:
- 方法一:
- 题目五:对称二叉树:
- 方法一:
- 题目五:另一颗树的子树:
- 方法一:
- 题目六:二叉树的前序遍历:
- 方法一:
- 拓展:
- 题目七:翻转二叉树:
- 方法一:
题目一:二叉树的销毁:
方法一:前序遍历:
1.前序遍历需要先销毁根节点:
2.在销毁节点之前需要保存左右节点:
3.通过保存的节点的地址再一次进入函数进行递归:
4.总结:相当于从上向下遍历:
//2.销毁://方法一:(先序的销毁)保存根节点的左右节点的地址销毁自己。
void BeforeTreeDestory(struct TreeNode* root)
{//1.根节点为空:if (root == NULL)return;//2.保存左右节点的根节点:struct TreeNode* left = root->left;struct TreeNode* right = root->right;free(root);//3.进入递归:BeforeTreeDestory(left);BeforeTreeDestory(right);
}
方法二:后序遍历:
1.左子树右子树根,左子树又有左子树右子树根。
2.到走到返回的时候,这个时候左和右的走完回来了就可以销毁当前树的根
3.总结:这是一个先到最然后再去从下到上的销毁。
4.好处:不需要像前序遍历去保存左右节点的地址再一次进入递归(在返回的时候就可以销毁节点)
//方法二:(后序遍历)先进入左右子树然后这是一种从下到上的销毁:
void EndTreeDestory(struct TreeNode* root)
{if (root = NULL)return;//进入左右子树回来才销毁:EndTreeDestory(root->left);EndTreeDestory(root->right);//销毁根节点:free(root);
}
题目二:二叉树查找值为x的节点
方法一:
1.使用先序遍历;
///
2.返回的条件:
1.根为空就返回说明没有找到:
2.找到值为x的节点返回节点的地址。
3.注意:数值不相同不需要返回说明还没有找到不需要返回:
3.返回的是节点的地址如果使用&& 和 || 逻辑运算符是不会返回地址的是只会返回0,1的这是需要注意的。
4.递归注意:因为我们需要返回节点的地址是需要从return一个节点之后从递归开辟的栈帧空间中带回来:
struct TreeNode* BinaryTreeFind(struct TreeNode* root, TreeNodeData x)
{//1.根节点为空:if (root == NULL)return NULL;//2.数值相同(找到值为X的节点不需要继续往下找了)://只有数值相同的根节点才会被返回回来:if (root->val == x)return root;//3.进入左右子树,这个数值到了非常深才可以被找到:struct TreeNode* tmp1 = BinaryTreeFind(root->left, x);if (tmp1 != NULL)return tmp1;struct TreeNode* tmp2 = BinaryTreeFind(root->right, x);if (tmp2 != NULL)return tmp2;//左右子树都没有找到的情况:return NULL;}
方法二:
1.在方法一的基础上进行优化:
2.你会发现根据上面的两个判断:
1.如果根节点为空就返回NULL
2.如果数据相同就返回节点
3.如果这颗树没有数值相同的节点就返回NULL
总结:不需要对函数返回值进行判空处理直接让返回值作为判断条件是空就不会进入语句里面,如果不是空就一定是数值相等的节点的地址。返回地址就没有问题。
struct TreeNode* BinaryTreeFind(struct TreeNode* root, TreeNodeData x)
{//1.根节点为空:if (root == NULL)return NULL;//2.数值相同(找到值为X的节点不需要继续往下找了)://只有数值相同的根节点才会被返回回来:if (root->val == x)return root;//方法二:struct TreeNode* tmp = NULL;tmp = BinaryTreeFind(root->left, x);if (tmp)return tmp;tmp = BinaryTreeFind(root->right, x);if (tmp)return tmp;return NULL;
}
方法三:
1.如果左子树没有节点的话就直接返回右子树的函数返回值就可以:
2.右子树中无非只有两个情况:
1.有数据返回固定的节点地址:
2.找到底没有数据返回NULL
所以右子树的返回就不需要去判断:
struct TreeNode* BinaryTreeFind(struct TreeNode* root, TreeNodeData x)
{//1.根节点为空:if (root == NULL)return NULL;//2.数值相同(找到值为X的节点不需要继续往下找了)://只有数值相同的根节点才会被返回回来:if (root->val == x)return root;//方法三:struct TreeNode* tmp = NULL;tmp = BinaryTreeFind(root->left, x);if (tmp)return tmp;return BinaryTreeFind(root->right, x);//1.返回值需要接受,层层接受。//2.防止返回值为空。//3.或和与的运算符返回的值是0/1 地址丢失!
}
题目三:层序遍历:
方法一:
1.层序顾名思义就是一层一层的去遍历数据:
2.可以使用队列的数据结构保存数据:、
3.让根带左右子树
4.在根节点被pop之前top出节点并且访问数值去打印并且将左右子树的根节点入队列:
5.当队列为空说明二叉树的所有节点已经被层序遍历完全了:
//4.层序遍历: 队列存储:
void LevelOrder(struct TreeNode* root)
{assert(root != NULL);//初始化队列:Que pQ;QueueInit(&pQ);//入根节点:QueuePush(&pQ, root);while (!QueueEmpty(&pQ)){//获取堆头的数据QueueDatatype top = QueueFront(&pQ);//打印队头数据:if(top!=NULL)printf("%d ", top->val);//出去之前把孩子带进来(不需要递归的!!!)if(top->left!=NULL)QueuePush(&pQ, top->left);if(top->right!=NULL)QueuePush(&pQ, top->right);//pop数据:QueuePop(&pQ);}//销毁队列:QueueDestor(&pQ);}
题目四:相同的树:
相同的树:题目链接
方法一:
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//1.如果两个都是空节点说明相同if(p==NULL && q==NULL)return true;//2.经过1的判断p,q中至少有一个不是空是有数值的://这样的情况如果进入一定是false。if(p==NULL || q==NULL)return false;//3.经过1,2的判断到这里一定满足两个节点都不是空节点。//两个情况://1.两个节点的值不相同返回false//2.两个节点的值相同但是还没有找完所有的节点所以继续进入递归寻找:if(p->val != q->val)return false;//4.如果两个 左子树对应已经有不相同的了就不需要进入右树了:return isSameTree(p->left,q->left) && isSameTree(p->right,q->right);
}
题目五:对称二叉树:
方法一:
1.这个题目和上面那个有一点点相似,这里比较一颗树的左右子树是否对称。上一个题目是比较直接给好的两个数的是否相同:
2.我们可以写一个子函数去传这一颗树的左右子树的根节点作为新的两颗树的根节点判断是否对称:
3.判断对称是判断相反的节点值是否相同(不同于判断俩颗树的相同相对位置的值是否相同)
对称二叉树:题目链接
bool isdouSymmetric(struct TreeNode* p ,struct TreeNode* q)
{//两个都为空,走到底了!if(p==NULL && q==NULL)return true;//一个空,一个不是空:if(p==NULL || q==NULL)return false;//两个都不是空:Lif(p->val != q->val)return false;//第一个是判断左数的左和右树的右的对称://第二个是判断左数的右和右树的左的对称return isdouSymmetric(p->left , q->right)&&isdouSymmetric( p->right ,q->left );
}bool isSymmetric(struct TreeNode* root){//写一个子函数进入左右子树:return isdouSymmetric(root->left,root->right);
}
题目五:另一颗树的子树:
另一颗树的子树:题目链接
方法一:
1.有两个树一个树是父母。一颗树是儿子在父母中有可能找到儿子。
2.注意二子要和父母中的这个树完全相同直到后面都为空了不能说一部分相同后面还有一部分不相同的两个树:
3.我们前面写过判断两个数是否相同的函数现在找到父母这个数子树中的一个根和待比较树的根节点的相同就有可能存在相同的子树。
4.当父母这个数到空就说明这颗子树没有相同的树包括没有数值的相等:
5.原函数使用 || 连接的好处是如果左树中有相同的子树并且返回了true就不需要再加入右树去判断,如果左树中没有相同的树还可以到右树中去寻找。只有左右都为false才返回false表示不存在相同的子树!
bool isSameTree(struct TreeNode* p, struct TreeNode* q){//1.两个空数if(q==NULL && p==NULL){return true;}//2.一个为空 另一个必须不为空:if(p==NULL || q==NULL){return false;}//3.两个数值一开始就不相等: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){//1.没有子树返回falseif(root==NULL)return false;//2.根节点的值相同有可能是相同子树的根节点:if(root->val == subRoot->val){if(isSameTree(root,subRoot)){return true;}}//进入递归(先序遍历):return isSubtree(root->left , subRoot)|| isSubtree(root->right , subRoot);
}
题目六:二叉树的前序遍历:
前序遍历:题目链接
方法一:
1.分析一下函数的参数和返回值:
1.返回一个数组的首地址(已经保存和前序遍历的数据)!
2.需要在堆区开辟空间这样才可以在外面找到这个数组的内容:
2.returnsize 返回数组的大小帮助外面去遍历数据:
3.使用计算节点个数的函数:
int TreeSize(struct TreeNode* root)
{return root==NULL? 0: TreeSize(root->left)+TreeSize(root->right)+1;
}void Traversal(struct TreeNode* root , int* tmp , int* i)
{if(root==NULL)return;tmp[*i]=root->val;(*i)++;Traversal(root->left , tmp , i);Traversal(root->right, tmp , i);
}int* preorderTraversal(struct TreeNode* root, int* returnSize){//1.开辟数组,返回顺序表长度int n=TreeSize(root);*returnSize = n;int* tmp=(int*)malloc(sizeof(int)*n);//2.给顺序表中添加内容:int i=0;Traversal(root , tmp , &i);return tmp;
}
拓展:
中序遍历:题目链接
后序遍历:题目链接
题目七:翻转二叉树:
翻转二叉树:题目链接
方法一:
1.不需要考虑左右子树为空的情况.
2.直接进行交换,下一次递归进入函数如果为空就会返回用了下一次函数判断当前为空的处理!
3.翻转是翻转每一颗树左右子树的根节点的情况!
void convert(struct TreeNode* root)
{if(root==NULL)return;struct TreeNode* tmp=NULL;tmp=root->left;root->left=root->right;root->right=tmp;convert(root->left);convert(root->right);
}struct TreeNode* invertTree(struct TreeNode* root){if(root==NULL)return root;convert(root);return root;
}
相关文章:

数据结构基础8:二叉树oj+层序遍历。
二叉树oj层序遍历 题目一:二叉树的销毁:方法一:前序遍历:方法二:后序遍历: 题目二:二叉树查找值为x的节点方法一:方法二:方法三: 题目三:层序遍历…...

Spring注解家族介绍:@RestController
前言: Spring Boot可以说是当前JAVA最为重要的一个框架,而Spring Boot的基石Spring中有着丰富的注解,因此我们会利用几篇文章来讲解我目前学到的各种注解,因此本类型文章的篇幅会比较短,主要着重于介绍各个注解。 目录…...

rocketmq
🍓代码仓库 https://gitee.com/xuhx615/rocket-mqdemo.git 🍓基本概念 ⭐生产者(Producer):消息发布者⭐主题(Topic):topic用于标识同一类业务类型的消息⭐消息队列(MessageQueue)…...

JAVA成员变量首字母小写,第二个字母大写报错问题(原因:Lombok与Spring冲突)
1、问题现象: JAVA类里定义成员变量使用首字母小写,第二个字母大写 Getter Setter public class BrandQueryObject extends QueryObject{private String pName; }结果页面报错,无法找到类型为 cn.wolfcode.ssm.query.BrandQueryObject 的对象…...

Python入门教程 |Python 错误和异常
Python3 错误和异常 作为 Python 初学者,在刚学习 Python 编程时,经常会看到一些报错信息,在前面我们没有提及,这章节我们会专门介绍。 Python 有两种错误很容易辨认:语法错误和异常。 Python assert(断…...

API商品接口对接使用:从理论到实践
随着电子商务的飞速发展,API商品接口已成为现代电子商务应用程序不可或缺的一部分。通过API商品接口,开发者可以轻松地从其他应用程序或服务中获取商品信息,实现快速、高效的电子商务功能。本文将探讨API商品接口的概念、对接使用的方法以及一…...

解决stable diffusion webui1.6 wd1.4 tagger加载失败的问题
由于webui源码的变化,需要修改两个地方的import 1.tagger/ui.py # 第十行 # from webui import wrap_gradio_gpu_call # 原代码 from modules.call_queue import wrap_gradio_gpu_call1.preload.py # 第4行开始 # from modules.shared import models_path # 原…...

Python学习-实现简单的http服务
基于Python实现一个简单的HttpServer,当用户在浏览器中输入IP地址:8000时,则会返回index.html页面内容,访问其它信息,则会返回错误信息(404) """ httpserver v1.0 1.获取来自浏览器的请求, 2.判断如果请求内容是 …...

#循循渐进学51单片机#变量进阶与点阵LED#not.6
1、掌握变量的作用域及存储类别。 局部变量 函数内部声明的变量,只在函数内部有效,在本函数以外是不能使用的,叫局部变量。 全局变量 在函数外部声明的变量就是全局变量,一个源程序可以包含一个或多个函数,全局变量…...

访问者模式
图片转载自 #include<iostream> using namespace std; #include<list> /*模板工厂单例化,所有的商品被注册进工厂中*/ /*访问者模式(行为型模式) 访问者,被访问者 visit accept 让访问变成一种操作,不同…...

epoll 的实现
epoll 这么好,为什么迟至 2.6 版本的 kernel 才支持(epoll manual: The epoll API was introduced in Linux kernel 2.5.44.)?2.4 版本的 kernel 不支持 epoll? 原因很简单,epoll 没什么神奇的。在早期没有太多的并发连接要处理&…...

怎么用excel管理固定资产
在当今的数字时代,我们已经习惯了使用各种电子工具来提高我们的生产力。其中,Excel无疑是一个强大的工具,它不仅可以帮助我们处理数据,还可以用来进行复杂的计算和分析。然而,你可能不知道的是,Excel也可以…...

记录crack某IDE插件过程
声明:本文仅记录学习过程,已对关键位置脱敏处理,未提供任何工具,请支持正版。 反编译jar包 使用cfr进行对插件核心jar包MyBxxxxxx-obfuss.jar进行反编译,在本地生成a.txt。 java -jar cfr-0.152.jar MyBxxxx-obfuss.…...

Android DEX相关,ART加载OAT文件
android .dex文件,对于Android DEX文件详细说明 Android dex、odex、oat、vdex、art区别 Android下的DEX文件和SO文件梳理总结 Android[art]-Android dex,odex,oat,vdex,art文件结构学习总结 第四章 常见的 Android 文件格式&…...

laravel框架 - 安装初步使用学习 composer安装
一、什么是laravel框架 Laravel框架可以开发各种不同类型的项目,内容管理系统(Content Management System,CMS)是一种比较典型的项目,常见的网站类型(如门户、新闻、博客、文章等)都可以利用CM…...

API实战教程:使用身份证OCR识别API构建一个应用
1. 引言 你是否曾经想过,只需拍一张身份证的照片,就能自动读取上面的所有信息?今天,我们要介绍的就是这样一个神奇的工具:身份证OCR识别API。不管你是技术小白还是初学者,跟着我们的步骤,你都可…...

前端-layui动态渲染表格行列与复杂表头合并
说在前面: 最近一直在用layui处理表格 写的有些代码感觉还挺有用的,顺便记录下来方便以后查看使用; HTML处代码 拿到id 渲染位置表格 <div class"layui-table-body salaryTable"><table class"layui-table" i…...

IDM(Internet Download Manager)下载器2024最新版本如何下载?
IDM(Internet Download Manager)下载器能够兼容支持多种浏览器进行文件下载,很多时候只要复制一个地址IDM的下载弹窗就自动弹出来,有时候不需要下载的时候也会弹,时间久了就会感觉很烦,不过这个问题其实可以…...

前端综合练手小项目
导读 本篇文章主要以小项目的方式展开,其中给出的代码中均包含详细地注释,大家可以参照理解。下面4个小项目中均包含有 HTML、CSS、JavaScript 等相关知识,可以拿来练手,系统提升一下自己的前端开发能力。 废话少说,…...

接口优化1
接口优化 文章目录 接口优化1. 内容概述2. 集成RabbitMQ2.1 下载2.2 SpringBoot集成RabbitMQ 快速入门1.相关配置2.创建发送者者和接收者 2.3 rabbitmq四种交换模式2.4 秒杀接口优化 1. 内容概述 核心思路:减少对数据库的访问,利用Redis的高并发特性来实现。 系统初…...

【无公网IP内网穿透】 搭建Emby媒体库服务器并远程访问「家庭私人影院」
目录 1.前言 2. Emby网站搭建 2.1. Emby下载和安装 2.2 Emby网页测试 3. 本地网页发布 3.1 注册并安装cpolar内网穿透 3.2 Cpolar云端设置 3.3 Cpolar内网穿透本地设置 4.公网访问测试 5.结语 1.前言 在现代五花八门的网络应用场景中,观看视频绝对是主力…...

QML android 采集手机传感器数据 并通过udp 发送
利用 qt 开发 安卓 app ,采集手机传感器数据 并通过udp 发送 #ifndef UDPLINK_H #define UDPLINK_H#include <QObject> #include <QUdpSocket> #include <QHostAddress>class UdpLink : public QObject {Q_OBJECT public:explicit UdpLink(QObjec…...

stableDiffusion安装
下载git 下载python-3.10.6版本 clone git至本地 使用git clone命令 git clone https://github.com/AUTOMATIC1111/stable-diffusion-webui 更换pip源为为百度镜像 pip config --global set global.index-url https://mirror.baidu.com/pypi/simple 最后的镜像源链接 阿里云 h…...

QT基础教程(QPushButton及信号与槽)
文章目录 前言一、信号与槽二、QPushButton总结 前言 本篇文章来带大家学习QPushbutton和信号与槽,其中信号与槽是QT中的核心也是比较重要的一个知识点。 资料合集地微信公众号:优质程序猿一、信号与槽 信号与槽(Signals and Slots&#x…...

Android 实战项目分享(一)用Android Studio绘制贝塞尔曲线的艺术之旅
一、项目概述 欢迎来到创意之源!我们精心打造的绘图应用程序将带你进入一个充满艺术和技术的奇妙世界。通过使用Android Studio,我们实现了绘制贝塞尔曲线的功能,让你能够轻松创作出令人惊叹的艺术作品。不论你是热爱绘画的大学生还是渴望学习…...

Windows系统关机后自动重启的解决方法
打开控制面板,找到【电源选项】; 方式一,打开Windows终端(管理员),输入“powercfg /h on”然后回车; 方式二,键盘按下开始键,搜索“控制面板”然后打开; 点击…...

微服务如何改变软件开发:实战经验与最佳实践分享
文章目录 什么是微服务?微服务实战经验1. 定义明确的服务边界2. 使用API网关3. 自动化部署和持续集成4. 监控和日志记录 微服务最佳实践1. 文档和通信2. 弹性设计3. 安全性4. 版本控制5. 监控和警报 微服务的未来 🎉欢迎来到架构设计专栏~微服务如何改变…...

安装深度(Deepin)系统
Deepin系统安装 Deepin是和Ubuntu一样,是一个基于Debian的Linux的发型版本。 Deepin相对于Ubuntu,Deepin更适合中国用户的使用习惯。 一 官网工具制作启动盘 制作启动盘、和安装系统,操作非常简单,nice! 官网提供了…...

Leetcode: 645.错误的集合 题解【超详细】
题目 集合 s 包含从 1 到 n 的整数。不幸的是,因为数据错误,导致集合里面某一个数字复制了成了集合里面的另外一个数字的值,导致集合 丢失了一个数字 并且 有一个数字重复 。 给定一个数组 nums 代表了集合 S 发生错误后的结果。 请你找出重复…...

闲鱼自动化软件——筛选/发送系统 V22已经测试完毕
更新 因为闲鱼版本更新,以及闲鱼整个程序维护记录,又增加了一些优化和提升的代码,所以又一次在整体上更新了一版闲鱼的此款软件。 主要更新点: 1、添加显示自定义按钮,可以自动显示最新数据,也可以手动翻…...