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

栈模拟先序后序中序遍历(非递归遍历)

先序遍历:

vector<int> preorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;while(stk.size()||u){if(u){res.push_back(u->val);//遍历当前结点stk.push(u);//记录当前递归层u=u->left;//遍历左子树}else {u=stk.top();stk.pop();//返回上一层递归层u=u->right;//遍历右子树}}return res;}

优化版:

vector<int> preorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;stk.push(u);while(stk.size()){auto t=stk.top();stk.pop();res.push_back(t->val);if(t->right)stk.push(t->right);//后遍历的先入栈,即右子树先入栈if(t->left)stk.push(t->left);//先遍历的后入栈,即左子树后入栈}return res;}

后序遍历:

后序遍历与先序遍历有互通之处,即后序遍历的倒序为:根右左。

所以我们可以把先序遍历的左右子树的遍历顺序倒一下便变成了后序遍历的倒序。

vector<int> postorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;while(stk.size()||u){if(u){res.push_back(u->val);//遍历当前结点stk.push(u);//记录下该层的遍历u=u->right;//先遍历右子树}else {u=stk.top();stk.pop();u=u->left;//再遍历左子树}}reverse(res.begin(),res.end());return res;}

同样有优化版:

vector<int> postorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(u==nullptr) return res;stk.push(u);while(stk.size()){TreeNode* t=stk.top();stk.pop();res.push_back(t->val);if(t->left)stk.push(t->left);if(t->right)stk.push(t->right);}reverse(res.begin(),res.end());return res;}

中序遍历:

vector<int> inorderTraversal(TreeNode* root) {vector<int>res;stack<TreeNode*>stk;while(stk.size()||root){if(root){stk.push(root);//相当于记录下了当前层递归root=root->left;//先遍历左子树}else{root=stk.top();//返回上一层递归stk.pop();res.push_back(root);//遍历当前结点root=root->right;//遍历右子树}}return res;}

中序遍历没有找到优化版,, 

相关文章:

栈模拟先序后序中序遍历(非递归遍历)

先序遍历&#xff1a; vector<int> preorderTraversal(TreeNode* u) {stack<TreeNode*>stk;vector<int>res;if(unullptr) return res;while(stk.size()||u){if(u){res.push_back(u->val);//遍历当前结点stk.push(u);//记录当前递归层uu->left;//遍历左…...

linux 内核软中断介绍

在介绍软中断之前&#xff0c;先来介绍一个概念&#xff1a;中断下半部&#xff1a; 为了避免处理复杂的中断嵌套&#xff0c;中断处理程序是在关闭中断的情况下执行的。可是&#xff0c;如果关闭中断的时间太长&#xff0c;可能导致中断请求丢失。例如周期时钟每隔 10 毫秒发送…...

软考:2024年软考高级:软件工程

软考&#xff1a;2024年软考高级: 提示&#xff1a;系列被面试官问的问题&#xff0c;我自己当时不会&#xff0c;所以下来自己复盘一下&#xff0c;认真学习和总结&#xff0c;以应对未来更多的可能性 关于互联网大厂的笔试面试&#xff0c;都是需要细心准备的 &#xff08;1…...

Kubernetes(K8s)_15_CNI

Kubernetes&#xff08;K8s&#xff09;_15_CNI CNI网络模型UnderlayMAC VLANIP VLANDirect Route OverlayVXLAN CNI插件FlannelCalico CNI配置内置实现 CNI CNI(Container Network Interface): 实现容器网络连接的规范 Kubernetes将网络通信可分为: Pod内容器、Pod、Pod与Se…...

python 生成器的作用

1. 生成器 参考&#xff1a; https://www.cainiaojc.com/python/python-generator.html 1.1. 什么是生成器&#xff1f; 在 python 中&#xff0c;一边循环一边计算的机制&#xff0c;称为生成器&#xff1a;generator. 1.2. 生成器有什么优点&#xff1f; 1、节约内存。p…...

第十五届蓝桥杯(Web 应用开发)模拟赛 2 期-大学组(详细分析解答)

目录 1.相不相等 1.1 题目要求 1.2 题目分析 1.3 源代码 2.三行情书 2.1 题目要求 2.2 题目分析 2.3 源代码 3.电影院在线订票 3.1 题目要求 3.2 题目分析 3.3 源代码 4.老虎坤&#xff08;不然违规发不出来&#xff09; 4.1 题目要求 4.2 题目分析 4.3 源代码 …...

图解系列--HTTPS,认证

确保 Web 安全的HTTPS 1.HTTP 的缺点 1.1.通信使用明文可能会被窃听 加密处理防止被窃听 加密的对象可以有这么几个。 (1).通信的加密 HTTP 协议中没有加密机制&#xff0c;但可以通过和 SSL&#xff08;Secure Socket Layer&#xff0c;安全套接层&#xff09;或TLS&#xff…...

element plus中表格的合计属性和例子

在 element plus 表格中&#xff0c;您可以使用 summary-method 属性来指定一个函数&#xff0c;计算表格中列的合计或平均值等。该函数应该返回一个对象&#xff0c;其中包含每个列的合计值。例如&#xff0c;如果您的表格数据是这样的&#xff1a; [{ name: John, age: 20, …...

计网Lesson1笔记

文章目录 几个简单概念计网的发展史阿帕网和RFCTCP/IP 协议互联网协议计网设计OSI 的七层架构TCP/IP 协议簇 几个简单概念 主机(host)&#xff1a;指单个计算机&#xff0c;比如PC&#xff0c;或者其他电子设备。端系统(end system)&#xff1a;指一块区域内的多个主机&#x…...

指针数组以及利用函数指针来实现简易计算器及typedef关键字(指针终篇)

文章目录 &#x1f680;前言&#x1f680;两段有趣的代码✈️typedef关键字 &#x1f680;指针数组&#x1f680;简易计算器的实现 &#x1f680;前言 基于阿辉前两篇博客指针的基础篇和进阶篇对于指针的了解&#xff0c;那么今天阿辉将为大家介绍C语言的指针剩下的部分&#…...

josef JZ-7Y-33静态中间继电器 电压DC220V 板前接线

系列型号&#xff1a; JZ-7Y-201X静态中间继电器&#xff1b;JZ-7J-201X静态中间继电器&#xff1b; JZ-7L-201X静态中间继电器&#xff1b;JZ-7D-201X静态中间继电器&#xff1b; JZ-7Y-201静态中间继电器&#xff1b;JZ-7J-201静态中间继电器&#xff1b; JZ-7L-201静态中…...

Java第二十章 ——多线程

本文主要讲了java中多线程的使用方法、线程同步、线程数据传递、线程状态及相应的一些线程函数用法、概述等。 在这之前&#xff0c;首先让我们来了解下在操作系统中进程和线程的区别&#xff1a;   进程&#xff1a;每个进程都有独立的代码和数据空间&#xff08;进程上下文…...

【超强笔记软件】Obsidian实现免费无限流量无套路云同步

【超强笔记软件】Obsidian如何实现免费无限流量无套路云同步&#xff1f; 目录 一、简介 软件特色演示&#xff1a; 二、使用免费群晖虚拟机搭建群晖Synology Drive服务&#xff0c;实现局域网同步 1 安装并设置Synology Drive套件 2 局域网内同步文件测试 三、内网穿透群…...

【Linux小项目】实现自己的bash

0. bash原理介绍 bash实际上就是一个负责解析输入字符串工具. 我们需要做的事是这些: 手动分割出输入的字符串判断哪些变量是内建命令(自己执行),哪些命令是普通命令(创建子进程执行)实现的功能有: echo export cd 常规指令 输入、输出流重定向 #include<stdio.h> #i…...

客户案例:EDLP助力金融行业打造高效数据防泄露体系

客户背景 某金融机构是一家以金融科技为核心&#xff0c;致力于为客户提供全方位、智能化、便捷化金融服务的综合性企业。公司总部位于南京&#xff0c;业务范围覆盖全国&#xff0c;拥有强大的技术研发团队和优秀的业务精英&#xff0c;为客户提供全方位的金融服务解决方案。 …...

【JavaFX漏扫开发基础】stage窗口/模式/模态

文章目录 stage一、stage窗口二、stage窗口,模式,模态stage模式(5种样式)模态化窗口stage stage其实就是一个窗口,它啥也不是,打开所有windows的程序都会有一个窗口,这个窗口就是javafx里的stage。里面的内容不属于stage,stage就是一个窗口,就这么简单。 Stage is a…...

MySQL进阶知识:锁

目录 前言 全局锁 表级锁 表锁 元数据锁&#xff08;MDL&#xff09; 意向锁 行级锁 行锁 行锁演示 间隙锁/临界锁 演示 前言 MySQL中的锁&#xff0c;按照锁的粒度分&#xff0c;分为以下三类 全局锁&#xff1a;锁定数据库中的所有表。表级锁&#xff1a;每次操…...

linux下的工具---gdb

一、gdb简介 GDB,是The GNU Project Debugger 的缩写&#xff0c;是 Linux 下功能全面的调试工具。 GDB支持断点、单步执行、打印变量、观察变量、查看寄存器、查看堆栈等调试手段。 程序的发布方式有两种&#xff0c;debug模式和release模式 Linux gcc/g出来的二进制程序&am…...

ESP32-Web-Server编程-JS 基础 2

ESP32-Web-Server编程-JS 基础 2 概述 上节介绍了 JS 编程的基础。如前所述&#xff0c;在 HTML 中&#xff0c;可以通过下述 两种方式使用 JS 程序&#xff1a; 直接在 HTML 文件中通过 script 标签中嵌入 JavaScript 代码。通过 src 元素引入外部的 JavaScript 文件。 在…...

Java Web基础教程

Java Web基础教程 1. Servlet基础 1.1 什么是Servlet Servlet是JavaEE中的标准组件之一&#xff0c;专门用于处理客户端的HTTP请求。并且它必须依赖于Servlet容器&#xff08;Tomcat就是一个标准的Servlet容器&#xff09;才能运行。因为Servlet实例的创建和销毁都是由容器负…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

CVPR 2025 MIMO: 支持视觉指代和像素grounding 的医学视觉语言模型

CVPR 2025 | MIMO&#xff1a;支持视觉指代和像素对齐的医学视觉语言模型 论文信息 标题&#xff1a;MIMO: A medical vision language model with visual referring multimodal input and pixel grounding multimodal output作者&#xff1a;Yanyuan Chen, Dexuan Xu, Yu Hu…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

树莓派超全系列教程文档--(62)使用rpicam-app通过网络流式传输视频

使用rpicam-app通过网络流式传输视频 使用 rpicam-app 通过网络流式传输视频UDPTCPRTSPlibavGStreamerRTPlibcamerasrc GStreamer 元素 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 使用 rpicam-app 通过网络流式传输视频 本节介绍来自 rpica…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

在rocky linux 9.5上在线安装 docker

前面是指南&#xff0c;后面是日志 sudo dnf config-manager --add-repo https://download.docker.com/linux/centos/docker-ce.repo sudo dnf install docker-ce docker-ce-cli containerd.io -y docker version sudo systemctl start docker sudo systemctl status docker …...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

Spring AI 入门:Java 开发者的生成式 AI 实践之路

一、Spring AI 简介 在人工智能技术快速迭代的今天&#xff0c;Spring AI 作为 Spring 生态系统的新生力量&#xff0c;正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务&#xff08;如 OpenAI、Anthropic&#xff09;的无缝对接&…...

MySQL 8.0 OCP 英文题库解析(十三)

Oracle 为庆祝 MySQL 30 周年&#xff0c;截止到 2025.07.31 之前。所有人均可以免费考取原价245美元的MySQL OCP 认证。 从今天开始&#xff0c;将英文题库免费公布出来&#xff0c;并进行解析&#xff0c;帮助大家在一个月之内轻松通过OCP认证。 本期公布试题111~120 试题1…...