二叉树的后序遍历(力扣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…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
突破不可导策略的训练难题:零阶优化与强化学习的深度嵌合
强化学习(Reinforcement Learning, RL)是工业领域智能控制的重要方法。它的基本原理是将最优控制问题建模为马尔可夫决策过程,然后使用强化学习的Actor-Critic机制(中文译作“知行互动”机制),逐步迭代求解…...
Xshell远程连接Kali(默认 | 私钥)Note版
前言:xshell远程连接,私钥连接和常规默认连接 任务一 开启ssh服务 service ssh status //查看ssh服务状态 service ssh start //开启ssh服务 update-rc.d ssh enable //开启自启动ssh服务 任务二 修改配置文件 vi /etc/ssh/ssh_config //第一…...
《从零掌握MIPI CSI-2: 协议精解与FPGA摄像头开发实战》-- CSI-2 协议详细解析 (一)
CSI-2 协议详细解析 (一) 1. CSI-2层定义(CSI-2 Layer Definitions) 分层结构 :CSI-2协议分为6层: 物理层(PHY Layer) : 定义电气特性、时钟机制和传输介质(导线&#…...
使用分级同态加密防御梯度泄漏
抽象 联邦学习 (FL) 支持跨分布式客户端进行协作模型训练,而无需共享原始数据,这使其成为在互联和自动驾驶汽车 (CAV) 等领域保护隐私的机器学习的一种很有前途的方法。然而,最近的研究表明&…...
电脑插入多块移动硬盘后经常出现卡顿和蓝屏
当电脑在插入多块移动硬盘后频繁出现卡顿和蓝屏问题时,可能涉及硬件资源冲突、驱动兼容性、供电不足或系统设置等多方面原因。以下是逐步排查和解决方案: 1. 检查电源供电问题 问题原因:多块移动硬盘同时运行可能导致USB接口供电不足&#x…...
蓝桥杯 冶炼金属
原题目链接 🔧 冶炼金属转换率推测题解 📜 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V,是一个正整数,表示每 V V V 个普通金属 O O O 可以冶炼出 …...
xmind转换为markdown
文章目录 解锁思维导图新姿势:将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件(ZIP处理)2.解析JSON数据结构3:递归转换树形结构4:Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...
Windows电脑能装鸿蒙吗_Windows电脑体验鸿蒙电脑操作系统教程
鸿蒙电脑版操作系统来了,很多小伙伴想体验鸿蒙电脑版操作系统,可惜,鸿蒙系统并不支持你正在使用的传统的电脑来安装。不过可以通过可以使用华为官方提供的虚拟机,来体验大家心心念念的鸿蒙系统啦!注意:虚拟…...
深度解析:etcd 在 Milvus 向量数据库中的关键作用
目录 🚀 深度解析:etcd 在 Milvus 向量数据库中的关键作用 💡 什么是 etcd? 🧠 Milvus 架构简介 📦 etcd 在 Milvus 中的核心作用 🔧 实际工作流程示意 ⚠️ 如果 etcd 出现问题会怎样&am…...
