二叉树的后序遍历(力扣145)
目录
题目描述:
解法一:递归法
解法二:迭代法
解法三:Morris遍历
二叉树的后序遍历
题目描述:
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。
示例 1:

输入:root = [1,null,2,3] 输出:[3,2,1]
示例 2:
输入:root = [] 输出:[]
示例 3:
输入:root = [1] 输出:[1]
提示:
- 树中节点的数目在范围
[0, 100]内 -100 <= Node.val <= 100
解法一:递归法
List<Integer> res = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {if(root == null){return res;}postorderTraversal(root.left);postorderTraversal(root.right);res.add(root.val);return res;}
复杂度分析
- 时间复杂度:O(n)O(n),其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度:O(n)O(n),为递归过程中栈的开销,平均情况下为 O(\log n)O(logn),最坏情况下树呈现链状,为 O(n)O(n)。
解法二:迭代法
public List<Integer> postorderTraversal1(TreeNode root) {List<Integer> res = new ArrayList<>();if(root == null){return res;}Deque<TreeNode> stack = new ArrayDeque<>();TreeNode cur = root;TreeNode prev = null;while(cur!=null || !stack.isEmpty()){while(cur != null){stack.push(cur);cur = cur.left;}cur = stack.pop();if(cur.right==null || prev==cur.right){res.add(cur.val);prev = cur;cur = null;}else{stack.push(cur);cur = cur.right;}}return res;}
复杂度分析
- 时间复杂度:O(n)O(n),其中 nn 是二叉搜索树的节点数。每一个节点恰好被遍历一次。
- 空间复杂度:O(n)O(n),为迭代过程中显式栈的开销,平均情况下为 O(\log n)O(logn),最坏情况下树呈现链状,为 O(n)O(n)。
解法三:Morris遍历
public List<Integer> postorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<Integer>();if (root == null) {return res;}TreeNode p1 = root, p2 = null;while (p1 != null) {p2 = p1.left;if (p2 != null) {while (p2.right != null && p2.right != p1) {p2 = p2.right;}if (p2.right == null) {p2.right = p1;p1 = p1.left;continue;} else {p2.right = null;addPath(res, p1.left);}}p1 = p1.right;}addPath(res, root);return res;}public void addPath(List<Integer> res, TreeNode node) {int count = 0;while (node != null) {++count;res.add(node.val);node = node.right;}int left = res.size() - count, right = res.size() - 1;while (left < right) {int temp = res.get(left);res.set(left, res.get(right));res.set(right, temp);left++;right--;}}
复杂度分析
- 时间复杂度:O(n)O(n),其中 nn 是二叉树的节点数。没有左子树的节点只被访问一次,有左子树的节点被访问两次。
- 空间复杂度:O(1)O(1)。只操作已经存在的指针(树的空闲指针),因此只需要常数的额外空间。
相关文章:
二叉树的后序遍历(力扣145)
目录 题目描述: 解法一:递归法 解法二:迭代法 解法三:Morris遍历 二叉树的后序遍历 题目描述: 给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。 示例 1: 输入:root …...
《Effective C++》读书纪实 -- 诸君同享
文章目录《Effective C》是一本经典的C编程指南,共包含50条C编程的最佳实践。 确定你的构造函数的行为 在构造函数中,应该尽可能地避免调用虚函数、非静态成员函数和虚基类的函数。 尽量使用const、enum、inline替换#define 使用const、enum、inline可以…...
【云原生】K8S-ConfigMap 实现应用和配置分离
文章目录前言ConfigMap 背景ConfigMap 创建方式ConfigMap 的使用使用 ConfigMap 的注意事项总结前言 Kubernetes 是目前最流行的容器编排系统之一,它提供了丰富的功能来支持容器化应用程序的管理和部署。 ConfigMap 是 Kubernetes 中重要的资源对象,用…...
java -测距工具(经纬度)
代码 /*** 测距工具* author qb*/ public class DistanceUtils {/*** 赤道半径*/private static final double EARTH_RADIUS 6378.137;private static double rad(double d) {return d * Math.PI / 180.0;}/*** Description : 通过经纬度获取距离(单位:米)* Group…...
postgres分区表的创建-基于继承
参考文档: http://postgres.cn/docs/12/ddl-partitioning.html 创建基于继承的分区表的步骤 1 创建父表 2 创建子表,从父表继承过来 3 创建函数及触发器,使插入的数据根据规则,插入到对应的子表中 -- 创建父表 CREATE TABLE a…...
Docker应用部署
文章目录Docker 应用部署一、部署MySQL二、部署Tomcat三、部署Nginx四、部署RedisDocker 应用部署 一、部署MySQL 搜索mysql镜像 docker search mysql拉取mysql镜像 docker pull mysql:5.6创建容器,设置端口映射、目录映射 # 在/root目录下创建mysql目录用于存…...
使用golang实现日志收集系统的logagent
整体架构 参考 七米老师的日志收集项目 主要用go实现logagent的部分,logagent的作用主要是实时监控日志追加的变化,并将变化发送到kafka中。 之前我们已经实现了 用go连接kafka并向其中发送数据,也实现了使用tail库监控日志追加操作。 我们…...
小红书点赞不显示怎么回事?小红书笔记评论被吞怎么办
小红书作为一个互联网产品,是一个软件。既然是软件就会有一定的程序漏洞,这是无法避免的。但是很多时候其实并不一定是漏洞的问题。今天就来和大家谈谈小红书点赞不显示怎么回事,小红书评论被吞又是怎么一回事,这些难道都是程序性…...
地址变换和缺页置换习题
1.设某进程页面的访问序列为4,3,2,1,4,3,5,4,3,2,1,5,当分配给该进程的内存页框数分别为3和4时,对于先进先出,最近最少使用,最佳页面置换算法,分别发生多少次缺页中断? 答: 分配的…...
PAT 乙级 1010 一元多项式求导(解题思路+AC代码)
题目: 设计函数求一元多项式的导数。(注:xn(n为整数)的一阶导数为nxn−1。) 输入格式: 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过 1000 的整数)。数字间以空格分…...
一维河流污染持续排放模拟(水污染扩散)
一、处理河道转换为geojson数据 以淮河为例处理示例数据: {"type": "FeatureCollection","features": [{"geometry": {"coordinates": [[[115.5803,34.4982],[115.5922,34.498],[115.6061,34.4994],[115.6203,…...
数据优化 | CnOpenDataA股上市公司招聘数据
就业是经济的“晴雨表”,更是社会的“稳定器”。稳定和扩大就业一直是国家宏观调控的重要目标,2021年中央经济工作会议八次提到“就业”这一关键词。在新冠肺炎疫情蔓延、世界经济下行及人口老龄化加快等多重因素的叠加之下,稳就业保民生成为…...
nacos和eureka的区别
nacos和eureka的区别 Eureka是什么 Eureka详解Nacos是什么 Nacos详解Nacos和Eureka的区别 CAP理论连接方式服务异常剔除操作实例方式自我保护机制 Eureka是什么 Eureka 是Spring Cloud 微服务框架默认的也是推荐的服务注册中心,由Netflix公司与2012将其开源出来,Eureka基于RE…...
canvas.toDataURL生成图片报错的解决方案
问题原因: toDataURL方法存在跨域限制,如果执行时dom内含有跨域的图片则浏览器执行时会报错。 这个根据不同的系统有不同的表现,例如:生成完毕但控制台有warning类型的警告,或者直接异常报error。 解决思路ÿ…...
电容笔和Apple pencil的区别是什么?好用电容笔推荐
Apple Pencil与目前市场上常见的电容笔最大的不同之处在于,普通电容笔并不具备苹果Pencil特有的重力压感,而仅仅是一种倾斜的压感。不过,其在其它方面的表现也很出色,与Apple Pencil相似,而且价格仅为200元。现在&…...
关于onnx 转ncnn 的问题
文章目录修改模型Detect层设计转换后处理优质文章由于有些操作是没法支持的 如5维的操作: Unsupported slice axes ! Unsupported slice axes ! Unsupported slice axes ! Unsupported slice axes ! Unsupported slice axes ! Unsupported slice axes !参考&#…...
设计模式之《责任链模式》
------《责任链模式》责任链模式的概念为什么用责任链模式工作中用在哪里设计思路代码实现总结责任链模式的概念 责任链模式是一种行为型设计模式,它允许你将请求沿着处理链传递,直到有一个处理者能够处理该请求为止。 在责任链模式中,每个…...
Android Studio实现多功能日记本
项目目录一、项目概述二、系统特点三、开发环境四、详细设计1、E-R图2、数据库3、系统设置五、运行演示一、项目概述 本次实现了功能实用且齐全的日记本,界面友好,使用便捷,采用MVC架构设计。使用SQLite数据库存储数据,数据表有主…...
只依赖Tensorrt和opencv的yolov5源代码
simple_yolo.hpp #ifndef SIMPLE_YOLO_HPP #define SIMPLE_YOLO_HPP/*简单的yolo接口,容易集成但是高性能 */#include <vector> #include <memory> #include <string> #include <future> #include <opencv2/opencv.hpp>namespace Si…...
多路I/O转接 poll(了解)
poll() 的机制与 select() 类似,与 select() 在本质上没有多大差别,管理多个描述符也是进行轮询,根据描述符的状态进行处理,但是 poll() 没有最大文件描述符数量的限制(但是数量过大后性能也是会下降)。 p…...
《Playwright:微软的自动化测试工具详解》
Playwright 简介:声明内容来自网络,将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具,支持 Chrome、Firefox、Safari 等主流浏览器,提供多语言 API(Python、JavaScript、Java、.NET)。它的特点包括&a…...
Nginx server_name 配置说明
Nginx 是一个高性能的反向代理和负载均衡服务器,其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机(Virtual Host)。 1. 简介 Nginx 使用 server_name 指令来确定…...
WordPress插件:AI多语言写作与智能配图、免费AI模型、SEO文章生成
厌倦手动写WordPress文章?AI自动生成,效率提升10倍! 支持多语言、自动配图、定时发布,让内容创作更轻松! AI内容生成 → 不想每天写文章?AI一键生成高质量内容!多语言支持 → 跨境电商必备&am…...
有限自动机到正规文法转换器v1.0
1 项目简介 这是一个功能强大的有限自动机(Finite Automaton, FA)到正规文法(Regular Grammar)转换器,它配备了一个直观且完整的图形用户界面,使用户能够轻松地进行操作和观察。该程序基于编译原理中的经典…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
Neko虚拟浏览器远程协作方案:Docker+内网穿透技术部署实践
前言:本文将向开发者介绍一款创新性协作工具——Neko虚拟浏览器。在数字化协作场景中,跨地域的团队常需面对实时共享屏幕、协同编辑文档等需求。通过本指南,你将掌握在Ubuntu系统中使用容器化技术部署该工具的具体方案,并结合内网…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
快速排序算法改进:随机快排-荷兰国旗划分详解
随机快速排序-荷兰国旗划分算法详解 一、基础知识回顾1.1 快速排序简介1.2 荷兰国旗问题 二、随机快排 - 荷兰国旗划分原理2.1 随机化枢轴选择2.2 荷兰国旗划分过程2.3 结合随机快排与荷兰国旗划分 三、代码实现3.1 Python实现3.2 Java实现3.3 C实现 四、性能分析4.1 时间复杂度…...
动态规划-1035.不相交的线-力扣(LeetCode)
一、题目解析 光看题目要求和例图,感觉这题好麻烦,直线不能相交啊,每个数字只属于一条连线啊等等,但我们结合题目所给的信息和例图的内容,这不就是最长公共子序列吗?,我们把最长公共子序列连线起…...
鸿蒙Navigation路由导航-基本使用介绍
1. Navigation介绍 Navigation组件是路由导航的根视图容器,一般作为Page页面的根容器使用,其内部默认包含了标题栏、内容区和工具栏,其中内容区默认首页显示导航内容(Navigation的子组件)或非首页显示(Nav…...
