当前位置: 首页 > news >正文

二叉树的遍历(先序遍历,中序遍历,后序遍历)递归与非递归算法

一、先序遍历

先序遍历:先遍历一颗树的根节点,后遍历左子树,最后遍历右子树


在这里插入图片描述

先序遍历序列: 1 -> 2 -> 4 -> 5 -> 3 -> 6 -> 7

题目链接

1.递归

分解子问题方法

class Solution {
public:void preOrder(TreeNode* root,vector<int>& str){if(root==NULL)return;str.push_back(root->val);preOrder(root->left,str);preOrder(root->right,str);}vector<int> preorderTraversal(TreeNode* root) {vector<int> str;preOrder(root,str);return str;}
};

在这里插入图片描述

2.非递归

思路:将一颗二叉树看做两个部分,一个部分是左路节点,另一个部分是左路节点的右子树,先将二叉树的左路节点全部入栈,再依次出栈,出栈的过程中将这个节点的右子树按相同方法将左路节点全部入栈,然后依次出栈,出栈的方法与上面相同,模拟递归调用的方法实现非递归,此时的入栈顺序就是先序遍历序列
在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<int> preorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur=root;vector<int> v;while(cur||!st.empty()){//访问一棵树的开始//  1、访问左路节点,左路节点入栈,后续一次访问左路节点的右子树while(cur){v.push_back(cur->val);st.push(cur);cur=cur->left;}//一次访问左路节点的右子树TreeNode* top=st.top();st.pop();//子问题的方式访问右子树cur=top->right;}return v;}
};

二、中序遍历

题目链接

中序遍历:先遍历一颗树的左子树,然后遍历根节点,最后遍历右子树
在这里插入图片描述

中序遍历序列:4 -> 2 -> 5 -> 1 -> 6 -> 3 -> 7

1.递归

递归调用分解子问题,与前序遍历递归思路相同

class Solution {
public:void inorder(TreeNode* root,vector<int>& res){if(root==NULL)return;inorder(root->left,res);res.push_back(root->val);inorder(root->right,res);}vector<int> inorderTraversal(TreeNode* root) {vector<int> res;inorder(root,res);return res;}
};

2.非递归

与前序遍历相似,前序遍历是在入栈的顺序为前序遍历序列,而中序遍历则是出栈的顺序则为中序遍历序列
在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<int> inorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur=root;vector<int> v;while(cur||!st.empty()){//访问一棵树的开始//  1、访问左路节点,左路节点入栈,后续一次访问左路节点的右子树while(cur){st.push(cur);cur=cur->left;}//一次访问左路节点的右子树TreeNode* top=st.top();st.pop();v.push_back(top->val);//子问题的方式访问右子树cur=top->right;}return v;}
};

三、后序遍历

后序遍历:先遍历一颗树的左子树,然后遍历右子树,最后遍历根节点
在这里插入图片描述

后续遍历序列:4 -> 5 -> 2 -> 6 -> 7 -> 3 -> 1

题目链接

1.递归

分解子问题

class Solution {
public:void postOrder(TreeNode* root,vector<int>& ret){if(root==NULL)return;postOrder(root->left,ret);postOrder(root->right,ret);ret.push_back(root->val);}vector<int> postorderTraversal(TreeNode* root) {vector<int> ret;postOrder(root,ret);return ret;}
};

2.非递归

后续遍历的非递归要比前序和中序遍历的非递归复杂一点,我们要在前面前序遍历和中序遍历非递归的算法上进行一些改进,创建一个变量prev,用来记录访问当前节点的上一个节点,如果当前左路节点的右子树为空或者已经访问过右子树就需将当前接节点出栈,此时的出栈顺序即为后续遍历序列。
在这里插入图片描述
在这里插入图片描述

class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {stack<TreeNode*> st;TreeNode* cur=root;TreeNode* prev=NULL;vector<int> v;while(cur||!st.empty()){//访问一棵树的开始//  1、访问左路节点,左路节点入栈,后续一次访问左路节点的右子树while(cur){st.push(cur);cur=cur->left;}TreeNode* top=st.top();//一个节点右子树为空或者上一个访问节点是右子树的根,说明右子树访问过滤,可以访问根节点了if(top->right==nullptr||top->right==prev){prev=top;v.push_back(top->val);st.pop();}else cur=top->right;}return v;}
};

相关文章:

二叉树的遍历(先序遍历,中序遍历,后序遍历)递归与非递归算法

目录 一、先序遍历题目链接1.递归2.非递归 二、中序遍历题目链接1.递归2.非递归 三、后序遍历题目链接1.递归2.非递归 一、先序遍历 先序遍历&#xff1a;先遍历一颗树的根节点&#xff0c;后遍历左子树&#xff0c;最后遍历右子树 先序遍历序列&#xff1a; 1 -> 2 -> 4…...

【LeetCode】516. 最长回文子序列

文章目录 1. 思路讲解1.1 创建dp表1.2 状态转移方程1.3 不需考虑边界问题 2. 整体代码 1. 思路讲解 1.1 创建dp表 此题采用动态规划的方法&#xff0c;创建一个二维dp表&#xff0c;dp[i][j]表示s[i, j]中最大回文子序列的长度。且我们人为规定 i 是一定小于等于 j 的。 1.2…...

Java 集合框架

Java 集合框架提供了一组接口和类&#xff0c;以实现各种数据结构和算法。 集合框架满足以下几个要求。 该框架必须是高性能的。基本集合&#xff08;动态数组&#xff0c;链表&#xff0c;树&#xff0c;哈希表&#xff09;的实现也必须是高效的。 该框架允许不同类型的集合…...

遇到多人协作,我们该用git如何应对?(版本二)

一、多人协作二 1.1多人协作 一般情况下&#xff0c;如果有多需求需要多人同时进行开发&#xff0c;是不会在一个分支上进行多人开发&#xff0c;而是一个需求或一个功能点就要创建一个feature 分支。 现在同时有两个需求需要你和你的小伙伴进行开发&#xff0c;那么你们俩便…...

Flutter iOS 集成使用 fluter boost

在 Flutter项目中集成完 flutter boost&#xff0c;并且已经使用了 flutter boost进行了路由管理&#xff0c;这时如果需要和iOS混合开发&#xff0c;这时就要到 原生端进行集成。 注意&#xff1a;之前建的项目必须是 Flutter module项目&#xff0c;并且原生项目和flutter m…...

node.js相关的npm包的集合

一、实用功能 1. qs 一个简单易用的字符串解析和格式化库 2.rxjs RxJS是一组模块化的库&#xff0c;用于使用 JavaScript 中的可观察集合和组合来组合异步和基于事件的程序。 3. mitt 微型 200b 功能事件发射器/发布订阅. 4.Underscore.js Underscore.js是一个用于 JavaScript…...

Android Ble蓝牙App(二)连接与发现服务

Ble蓝牙App&#xff08;二&#xff09;连接与发现服务 前言正文一、GATT回调二、连接和断连三、连接状态回调四、发现服务五、服务适配器六、显示服务七、源码 前言 在上一篇中我们进行扫描设备的处理&#xff0c;本文中进行连接和发现服务的数据处理&#xff0c;运行效果图如下…...

Android 自定义按钮(可滑动、点击)

按钮图片素材 https://download.csdn.net/download/Lan_Se_Tian_Ma/88151085 px 和 dp 转换工具类&#xff08;Java&#xff09; // px 和 dp 转换工具类 public class DensityUtil {/*** 根据手机的分辨率从 dip 的单位 转成为 px(像素)*/public static int dip2px(Conte…...

mac录屏怎么打开?很简单,让我来教你!

mac电脑作为一款广受欢迎的电脑系统&#xff0c;提供了多种方式来满足用户录屏的需求。无论您是要录制教学视频、制作演示文稿&#xff0c;还是记录游戏精彩瞬间&#xff0c;mac电脑都能帮助您实现这些目标。本文将为您介绍两种mac录屏的方法。通过本文的指导&#xff0c;您将能…...

Stable Diffusion AI绘画学习指南【插件安装设置】

插件安装的方式 可用列表方式安装&#xff0c;点开Extensions 选项卡&#xff0c;找到如下图&#xff0c;找到Available选项卡&#xff0c;点load from加载可用插件&#xff0c;在可用插件列表中找到要装的插件按install 按扭按装&#xff0c;安装完后(Apply and restart UI)应…...

APP开发中的性能优化:提升用户满意度的关键

APP开发中的性能优化是需要持续进行的&#xff0c;它不仅能够让用户体验到 APP的使用感受&#xff0c;还能在一定程度上提升用户的满意度&#xff0c;从而提升 APP的粘性和转化率。不过在实际开发中&#xff0c;很多 APP开发公司会存在性能优化上的问题&#xff0c;这就需要了解…...

Golang 切片 常用方法

文章目录 移除指定位置的元素查找元素的位置查找最大最小的元素去重随机打乱排序二维排序sort.Sort 排序 下面的方法省略一些校验&#xff0c;如数组越界等&#xff0c;且都采用泛型(要求go版本 > 1.18) 移除指定位置的元素 package mainimport ("fmt" )func Del…...

【Linux后端服务器开发】poll/epoll多路转接IO服务器

目录 一、poll原理 二、poll实现多路转接IO服务器 三、epoll函数接口 四、epoll的工作原理 五、epoll实现多路转接IO服务器 一、poll原理 poll函数接口 #include <poll.h> int poll(struct pollfd *fds, nfds_t nfds, int timeout);// pollfd结构 struct pollfd …...

【设计模式——学习笔记】23种设计模式——命令模式Command(原理讲解+应用场景介绍+案例介绍+Java代码实现)

文章目录 案例引入介绍基础介绍登场角色 案例实现案例一实现 案例二介绍实现拓展 命令模式在JdbcTemplate源码中的应用总结文章说明 案例引入 有一套智能家电&#xff0c;其中有照明灯、风扇、冰箱、洗衣机&#xff0c;这些智能家电来自不同的厂家&#xff0c;我们不想针对每一…...

Rust中的高吞吐量流处理

本篇文章主要介绍了Rust中流处理的概念、方法和优化。作者不仅介绍了流处理的基本概念以及Rust中常用的流处理库&#xff0c;还使用这些库实现了一个流处理程序。 最后&#xff0c;作者介绍了如何通过测量空闲和阻塞时间来优化流处理程序的性能&#xff0c;并将这些内容同步至…...

探索编程世界的宝藏:程序员必掌握的20大算法

文章目录 1 引言2 冒泡排序算法&#xff1a;编程世界的排序魔法 &#x1f9d9;‍♀️&#x1f522;3 选择排序算法&#xff1a;排序世界的精确挑选器 &#x1f3af;&#x1f522;4 插入排序算法&#xff1a;排序世界的巧妙插珠者 ✨&#x1f522;5 快速排序算法&#xff1a;排序…...

Android NFC通信示例

前言 近距离无线通信 (NFC) 是一组近距离无线技术&#xff0c;通常只有在距离不超过 4 厘米时才能启动连接。借助 NFC&#xff0c;您可以在 NFC 标签与 Android 设备之间或者两台 Android 设备之间共享小型负载。 支持 NFC 的 Android 设备同时支持以下三种主要操作模式&…...

2023年08月IDE流行度最新排名

点击查看最新IDE流行度最新排名&#xff08;每月更新&#xff09; 2023年08月IDE流行度最新排名 顶级IDE排名是通过分析在谷歌上搜索IDE下载页面的频率而创建的 一个IDE被搜索的次数越多&#xff0c;这个IDE就被认为越受欢迎。原始数据来自谷歌Trends 如果您相信集体智慧&am…...

使用Beego和MySQL实现帖子和评论的应用,并进行接口测试(附源码和代码深度剖析)

文章目录 小项目介绍源码分析main.gorouter.gomodels/user.gomodels/Post.gomodels/comment.gocontrollers/post.gocontrollers/comment.go 接口测试测试增加帖子测试查看帖子测试增加评论测试查看评论 小项目介绍 经过对需求的分析&#xff0c;我增加了一些额外的东西&#x…...

物联网潜在的巨大价值在于大数据分析

物联网潜在的巨大价值在于大数据分析 从数据里去挖掘市场或者用户的精准需求。 往小的说&#xff0c;后台可以统计用户家里各各插座一年甚至更久的用电情况&#xff0c;这些数据也可以通过app或者小程序展现给用户。 用户可以很直观看到自己一年的用电情况&#xff0c;哪个家…...

【JavaEE】-- HTTP

1. HTTP是什么&#xff1f; HTTP&#xff08;全称为"超文本传输协议"&#xff09;是一种应用非常广泛的应用层协议&#xff0c;HTTP是基于TCP协议的一种应用层协议。 应用层协议&#xff1a;是计算机网络协议栈中最高层的协议&#xff0c;它定义了运行在不同主机上…...

全球首个30米分辨率湿地数据集(2000—2022)

数据简介 今天我们分享的数据是全球30米分辨率湿地数据集&#xff0c;包含8种湿地亚类&#xff0c;该数据以0.5X0.5的瓦片存储&#xff0c;我们整理了所有属于中国的瓦片名称与其对应省份&#xff0c;方便大家研究使用。 该数据集作为全球首个30米分辨率、覆盖2000–2022年时间…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院查看报告小程序

一、开发环境准备 ​​工具安装​​&#xff1a; 下载安装DevEco Studio 4.0&#xff08;支持HarmonyOS 5&#xff09;配置HarmonyOS SDK 5.0确保Node.js版本≥14 ​​项目初始化​​&#xff1a; ohpm init harmony/hospital-report-app 二、核心功能模块实现 1. 报告列表…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

管理学院权限管理系统开发总结

文章目录 &#x1f393; 管理学院权限管理系统开发总结 - 现代化Web应用实践之路&#x1f4dd; 项目概述&#x1f3d7;️ 技术架构设计后端技术栈前端技术栈 &#x1f4a1; 核心功能特性1. 用户管理模块2. 权限管理系统3. 统计报表功能4. 用户体验优化 &#x1f5c4;️ 数据库设…...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

推荐 github 项目:GeminiImageApp(图片生成方向&#xff0c;可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

scikit-learn机器学习

# 同时添加如下代码, 这样每次环境(kernel)启动的时候只要运行下方代码即可: # Also add the following code, # so that every time the environment (kernel) starts, # just run the following code: import sys sys.path.append(/home/aistudio/external-libraries)机…...

Python+ZeroMQ实战:智能车辆状态监控与模拟模式自动切换

目录 关键点 技术实现1 技术实现2 摘要&#xff1a; 本文将介绍如何利用Python和ZeroMQ消息队列构建一个智能车辆状态监控系统。系统能够根据时间策略自动切换驾驶模式&#xff08;自动驾驶、人工驾驶、远程驾驶、主动安全&#xff09;&#xff0c;并通过实时消息推送更新车…...

群晖NAS如何在虚拟机创建飞牛NAS

套件中心下载安装Virtual Machine Manager 创建虚拟机 配置虚拟机 飞牛官网下载 https://iso.liveupdate.fnnas.com/x86_64/trim/fnos-0.9.2-863.iso 群晖NAS如何在虚拟机创建飞牛NAS - 个人信息分享...