当前位置: 首页 > 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;哪个家…...

Vue记事本应用实现教程

文章目录 1. 项目介绍2. 开发环境准备3. 设计应用界面4. 创建Vue实例和数据模型5. 实现记事本功能5.1 添加新记事项5.2 删除记事项5.3 清空所有记事 6. 添加样式7. 功能扩展&#xff1a;显示创建时间8. 功能扩展&#xff1a;记事项搜索9. 完整代码10. Vue知识点解析10.1 数据绑…...

java_网络服务相关_gateway_nacos_feign区别联系

1. spring-cloud-starter-gateway 作用&#xff1a;作为微服务架构的网关&#xff0c;统一入口&#xff0c;处理所有外部请求。 核心能力&#xff1a; 路由转发&#xff08;基于路径、服务名等&#xff09;过滤器&#xff08;鉴权、限流、日志、Header 处理&#xff09;支持负…...

相机Camera日志实例分析之二:相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

渗透实战PortSwigger靶场-XSS Lab 14:大多数标签和属性被阻止

<script>标签被拦截 我们需要把全部可用的 tag 和 event 进行暴力破解 XSS cheat sheet&#xff1a; https://portswigger.net/web-security/cross-site-scripting/cheat-sheet 通过爆破发现body可以用 再把全部 events 放进去爆破 这些 event 全部可用 <body onres…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

Springcloud:Eureka 高可用集群搭建实战(服务注册与发现的底层原理与避坑指南)

引言&#xff1a;为什么 Eureka 依然是存量系统的核心&#xff1f; 尽管 Nacos 等新注册中心崛起&#xff0c;但金融、电力等保守行业仍有大量系统运行在 Eureka 上。理解其高可用设计与自我保护机制&#xff0c;是保障分布式系统稳定的必修课。本文将手把手带你搭建生产级 Eur…...

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...