二叉树三种遍历的递归与非递归写法
目录
编辑
一,前序遍历
题目接口:
递归解法:
非递归解法:
二,中序遍历
题目接口:
递归解法:
非递归写法:
三,后序遍历
题目接口:
递归解法:
非递归解法:
一,前序遍历
题目接口:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {}
};
递归解法:
对于这道题,相信大家都能够轻松解决掉。递归写法,非常简单:
class Solution {
public:void _preorderTraversal(TreeNode*root, vector<int>&ret){if(root == nullptr){return ;}ret.push_back(root->val);_preorderTraversal(root->left, ret);_preorderTraversal(root->right,ret);}vector<int> preorderTraversal(TreeNode* root) {vector<int>ret;_preorderTraversal(root,ret);return ret;}
};
非递归解法:
但是,如果要你写出一个非递归版本的的写法呢?我们该如何写呢?步骤如下:
1. 搞一个栈,这个栈的作用是存下每一个节点。
2.定义一个cur指针,指向当前节点。然后从该节点cur开始,使用一个小循环循环遍历左子树,在将一个左子树遍历完以后也就是遍历到nullptr以后便结束循环。
3.取栈顶元素top,让cur重新指向top的右指针。然后从新的cur开始重新遍历左子树。
4.当栈为空且cur为nullptr时便可以结束大循环,返回得到的前序遍历的结果。
代码如下:
class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {vector<int>ret;//存储结果的数组stack<TreeNode*>st;//栈TreeNode*cur = root;while(!st.empty()||cur)//循环结束条件,必须在两者都是nullptr的情况下才能结束循环。{while(cur){ret.push_back(cur->val);st.push(cur);cur = cur->left;}TreeNode* top = st.top();st.pop();cur = top->right;//指向右节点,遍历右树。}return ret;}
};
总结,这里的关键一步便是遍历每一个节点的左树。然后将每一个节点用栈记录下来。这里为什么要使用栈呢?这是利用了栈后进先出的特点!!!由于在电脑上画图比较麻烦,所以大家可以自己根据这个代码画图模拟一下。
二,中序遍历
题目接口:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {}
};
递归解法:
使用递归解法任仍然是简单的,也就是按照顺序左子树->根->右子树的顺序来递归遍历这棵二叉树。代码如下:
class Solution {
public:void _inorderTraversal(TreeNode*root, vector<int>&in){if(root == nullptr){return;}_inorderTraversal(root->left,in);in.push_back(root->val);_inorderTraversal(root->right,in);}vector<int> inorderTraversal(TreeNode* root) {vector<int>in;_inorderTraversal(root,in);return in;}
};
非递归写法:
有了上面的前序遍历的非递归写法的思想以后,中序遍历的非递归写法就好写很多了。我们只需要在前序遍历的非递归写法上改一下根节点插入到in数组中的顺序便可以了。代码如下:
class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {vector<int>ret;//存储结果的数组stack<TreeNode*>st;//栈TreeNode*cur = root;while(!st.empty()||cur)//循环结束条件,必须在两者都是nullptr的情况下才能结束循环。{while(cur)//这个循环只往栈st里面插入插入节点的指针而不往ret里面插入值{st.push(cur);cur = cur->left;}TreeNode* top = st.top();ret.push_back(top->val);//在这里才插入值st.pop();cur = top->right;//指向右节点,遍历右树。}return ret;}
};
三,后序遍历
题目接口:
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {}
};
递归解法:
这道题的递归解法仍然很简单,就是按照左子树->右子树->根的顺序遍历这棵二叉树。递归代码如下:
class Solution {
public:void _postorderTraversal(TreeNode*root,vector<int>&ret){if(root == nullptr){return;}_postorderTraversal(root->left,ret);_postorderTraversal(root->right,ret);ret.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int>ret;_postorderTraversal(root,ret);return ret;}
};
非递归解法:
这道题难就难在非递归解法的代码我们该如何去写呢?难就难在这里了。首先我们也都知道,后序布遍历的遍历顺序是:左子树->右子树->根。所以我们仍然要先访问左子树。我们仍然要先访问左,先把所有的左节点插入到栈里面。这一步其实和前面的中序遍历与前序遍历的思路是一样的,但是在后序遍历里面是否能够访问当前节点是要做判断的:当前节点必须在右节点被访问以后才能访问。
代码如下:
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*>st;vector<int>ret;TreeNode*cur = root;TreeNode*prev = nullptr;//记录前面访问了那一个节点while(!st.empty()||cur){while(cur)//只插入不访问{st.push(cur);cur = cur->left;}TreeNode* top = st.top();//找到最后一个插入栈的节点if(prev == top->right)//如果这个节点的右节点已经被访问过来,这个节点便是可以访问的{prev = top;//更新prevret.push_back(top->val);st.pop();}else//如果这个节点的右节点没有被访问过,便先访问右节点(右树){cur = top->right;prev = cur;//更新prev}}return ret;}
};
相关文章:
二叉树三种遍历的递归与非递归写法
目录 编辑 一,前序遍历 题目接口: 递归解法: 非递归解法: 二,中序遍历 题目接口: 递归解法: 非递归写法: 三,后序遍历 题目接口: 递归解法&…...
虹科 | 解决方案 | 汽车示波器 远程诊断方案
车厂总部专家实时指导你修车 当一线汽修技师遇到疑难问题无从下手时,可以准备好pico汽车示波器套装,并戴上我们的M400智能AR眼镜,通过语音操作,呼叫主机厂的技术支持老师;老师通过AR眼镜上的摄像头老师可以实时看到现…...
Unity ScrollView最底展示
Unity ScrollView最底展示 问题方案逻辑 问题 比如在做聊天界面的时候我们肯定会使用到ScrollView来进行展示我们的聊天内容,那么这个时候来新消息的时候就需要最底展示,我认为这里有两种方案; 一种是通过算法每一条预制体的高度*一共多少…...
linux常用基本命令大全的使用(三)
🎬作者简介:大家好,我是青衿🥇 ☁️博客首页:CSDN主页石马农青衿 🌄每日一句:努力一点,优秀一点 📑前言 本文主要是linux常用基本命令面试篇文章,如果有什么…...
Qt 实现软件启动界面动画
实现软件启动界面,用到QSplashScreen类。 效果 启动界面 描述 QSplashScreen小部件提供了一个可以在应用程序启动期间显示的启动画面。 启动画面通常是在应用程序启动时显示的小部件。启动画面通常用于启动时间较长的应用程序(例如需要花费一些时间来建…...
2000-2021年三批“智慧城市”试点名单匹配数据
2000-2021年三批“智慧城市”试点名单匹配数据 1、时间:2000-2021年 2、指标:行政区划代码、地区、所属省份、年份、智慧城市试点、最早试点年份 3、来源:住建部公布的三批“国家智慧城市名单” 4、说明:内含原始文件和匹配结…...
H5游戏分享-烟花效果
<!DOCTYPE html> <html dir"ltr" lang"zh-CN"> <head> <meta charset"UTF-8" /> <meta name"viewport" content"widthdevice-width" /> <title>点击夜空欣赏烟花</title> <sc…...
底层驱动day8作业
代码: //驱动程序 #include<linux/init.h> #include<linux/module.h> #include<linux/of.h> #include<linux/of_gpio.h> #include<linux/gpio.h> #include<linux/timer.h>struct device_node *dnode; //unsigned int gpiono; …...
openWRT SFTP 实现远程文件安全传输
🔥博客主页: 小羊失眠啦. 🔖系列专栏: C语言、Linux、 Cpolar ❤️感谢大家点赞👍收藏⭐评论✍️ 文章目录 前言 1. openssh-sftp-server 安装2. 安装cpolar工具3.配置SFTP远程访问4.固定远程连接地址 前言 本次教程我…...
麒麟KYLINOS2303版本上使用KDE桌面共享软件
原文链接:麒麟KYLINOS2303版本上使用KDE桌面共享软件 hello,大家好啊,今天给大家推荐一个在麒麟KYLINOS桌面操作系统2303版本上使用KDE桌面共享软件的文章,通过安装KDE桌面共享软件,可以让远程vnc客户端连接访问本机桌…...
H5游戏源码分享-手机捉鬼游戏
H5游戏源码分享-手机捉鬼游戏 一款考验手速的游戏 <!DOCTYPE html> <html><head><meta http-equiv"Content-Type" content"text/html; charsetUTF-8"><title>手机捉鬼 微信HTML5在线朋友圈游戏</title><meta name&…...
vite中将css,js文件归类至文件夹
build: {chunkSizeWarningLimit: 1500,rollupOptions: {output: {// 最小化拆分包manualChunks(id) {if (id.includes(node_modules)) {return id.toString().split(node_modules/)[1].split(/)[0].toString()}},// 用于从入口点创建的块的打包输出格式[name]表示文件名,[hash]…...
【通信原理】第一章|绪论|信息度量和通信系统的性能指标
前言 那么这里博主先安利一些干货满满的专栏了! 首先是博主的高质量博客的汇总,这个专栏里面的博客,都是博主最最用心写的一部分,干货满满,希望对大家有帮助。 高质量博客汇总 绪论 1. 信息和信息的度量 定义信息…...
基于STM32+OneNet设计的物联网智能鱼缸(2023升级版)
基于STM32+OneNet设计的智能鱼缸(升级版) 一、前言 随着物联网技术的快速发展,智能家居和智能养殖领域的应用越来越广泛。智能鱼缸作为智能家居和智能养殖的结合体,受到了越来越多消费者的关注。本项目设计一款基于STM32的物联网智能鱼缸,通过集成多种传感器和智能化控制模…...
NET-MongoDB的安装使用
一.下载 MongoDB 点击 Select package 选择自己所需版本后点击下载,本文选用Windows 6.0版本以上 二、配置MongoDB 在 Windows 上,MongoDB 将默认安装在 C:\Program Files\MongoDB 中。 将 C:\Program Files\MongoDB\Server\version_numbe…...
简化geojson策略
1、删除无用的属性,也就是字段,在shp的时候就给删了 用arcgis等等软件都可以做到 2、简化坐标的小数位数 (1)网上推荐的办法,俺不会Python… github.com/perrygeo/geojson-precision (2)曲线…...
一个Binder的前生今世 (二):Binder进程和线程的创建
文章目录 一个Binder的前生今世 (二):Binder进程和线程的创建binder在进程中的启动小结注释一个Binder的前生今世 (二):Binder进程和线程的创建 前篇文章一个Binder的前生今世 (一):Service的创建 讲了一个Service是如何创建以及如何与客户端建立联系的。讲解中涉及到…...
RocketMq源码分析(八)--消息消费流程
文章目录 一、消息消费实现二、消息消费过程1、消息拉取2、消息消费1)提交消费请求2)消费消息 一、消息消费实现 消息消费有2种实现,分别为:并发消费实现(ConsumeMessageConcurrentlyService)和顺序消费实现…...
sql--索引使用
最左前缀法则(联合索引) 联合索引 位置不影响,但是所有索引必须连续使用,才会走索引 中间跳过则会造成后面索引则会失效 索引失效 规避方法---尽量使用> 或 < Explain需要重点关注的字段 Type key_leng possibl…...
alibaba.fastjson的使用(三)-- Map、List ==》JSON字符串
目录 1.使用到的方法为: 2. Map转JSON字符串 3. List转JSON字符串 1.使用到的方法为: static String toJSONString(Object object) 2. Map转JSON字符串 /**...
SpringCloudGateway 自定义局部过滤器
场景: 将所有请求转化为同一路径请求(方便穿网配置)在请求头内标识原来路径,然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...
vue3+vite项目中使用.env文件环境变量方法
vue3vite项目中使用.env文件环境变量方法 .env文件作用命名规则常用的配置项示例使用方法注意事项在vite.config.js文件中读取环境变量方法 .env文件作用 .env 文件用于定义环境变量,这些变量可以在项目中通过 import.meta.env 进行访问。Vite 会自动加载这些环境变…...
React---day11
14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store: 我们在使用异步的时候理应是要使用中间件的,但是configureStore 已经自动集成了 redux-thunk,注意action里面要返回函数 import { configureS…...
R语言速释制剂QBD解决方案之三
本文是《Quality by Design for ANDAs: An Example for Immediate-Release Dosage Forms》第一个处方的R语言解决方案。 第一个处方研究评估原料药粒径分布、MCC/Lactose比例、崩解剂用量对制剂CQAs的影响。 第二处方研究用于理解颗粒外加硬脂酸镁和滑石粉对片剂质量和可生产…...
QT3D学习笔记——圆台、圆锥
类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体(对象或容器)QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质(定义颜色、反光等)QFirstPersonC…...
HubSpot推出与ChatGPT的深度集成引发兴奋与担忧
上周三,HubSpot宣布已构建与ChatGPT的深度集成,这一消息在HubSpot用户和营销技术观察者中引发了极大的兴奋,但同时也存在一些关于数据安全的担忧。 许多网络声音声称,这对SaaS应用程序和人工智能而言是一场范式转变。 但向任何技…...
安卓基础(Java 和 Gradle 版本)
1. 设置项目的 JDK 版本 方法1:通过 Project Structure File → Project Structure... (或按 CtrlAltShiftS) 左侧选择 SDK Location 在 Gradle Settings 部分,设置 Gradle JDK 方法2:通过 Settings File → Settings... (或 CtrlAltS)…...
uni-app学习笔记三十五--扩展组件的安装和使用
由于内置组件不能满足日常开发需要,uniapp官方也提供了众多的扩展组件供我们使用。由于不是内置组件,需要安装才能使用。 一、安装扩展插件 安装方法: 1.访问uniapp官方文档组件部分:组件使用的入门教程 | uni-app官网 点击左侧…...
车载诊断架构 --- ZEVonUDS(J1979-3)简介第一篇
我是穿拖鞋的汉子,魔都中坚持长期主义的汽车电子工程师。 老规矩,分享一段喜欢的文字,避免自己成为高知识低文化的工程师: 做到欲望极简,了解自己的真实欲望,不受外在潮流的影响,不盲从,不跟风。把自己的精力全部用在自己。一是去掉多余,凡事找规律,基础是诚信;二是…...
门静脉高压——表现
一、门静脉高压表现 00:01 1. 门静脉构成 00:13 组成结构:由肠系膜上静脉和脾静脉汇合构成,是肝脏血液供应的主要来源。淤血后果:门静脉淤血会同时导致脾静脉和肠系膜上静脉淤血,引发后续系列症状。 2. 脾大和脾功能亢进 00:46 …...
