( “树” 之 前中后序遍历) 145. 二叉树的后序遍历 ——【Leetcode每日一题】
基础概念:前中后序遍历
1/ \2 3/ \ \
4 5 6
- 层次遍历顺序:[1 2 3 4 5 6]
- 前序遍历顺序:[1 2 4 5 3 6]
- 中序遍历顺序:[4 2 5 1 3 6]
- 后序遍历顺序:[4 5 2 6 3 1]
层次遍历使用 BFS 实现,利用的就是 BFS 一层一层遍历的特性;而前序、中序、后序遍历利用了 DFS 实现。
前序、中序、后序遍只是在对节点访问的顺序有一点不同,其它都相同。
① 前序
void dfs(TreeNode root) {visit(root);dfs(root.left);dfs(root.right);
}
② 中序
void dfs(TreeNode root) {dfs(root.left);visit(root);dfs(root.right);
}
③ 后序
void dfs(TreeNode root) {dfs(root.left);dfs(root.right);visit(root);
}
145. 二叉树的后序遍历
给你一棵二叉树的根节点 root ,返回其节点值的 后序遍历 。

输入:root = [1,null,2,3]
输出:[3,2,1]
示例 2:
输入:root = []
输出:[]
示例 3:
输入:root = [1]
输出:[1]
提示:
- 树中节点的数目在范围 [0, 100] 内
- -100 <= Node.val <= 100
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
思路:
法一:DFS
- 递归,见上面的基础概念。
法二:迭代
后序的迭代遍历可以理解成 ” 前序遍历 “ 的反转:(前序遍历)
- 这个 ”前序遍历 “ 的遍历顺序为:根节点,右子树、左子树
代码:(Java、C++)
法一:递归
Java
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public List<Integer> ans = new ArrayList<>();public List<Integer> postorderTraversal(TreeNode root) {dfs(root);return ans;}public void dfs(TreeNode root){if(root == null) return;dfs(root.left);dfs(root.right);ans.add(root.val);}
}
C++
/*** Definition for a binary tree node.* struct TreeNode {* int val;* TreeNode *left;* TreeNode *right;* TreeNode() : val(0), left(nullptr), right(nullptr) {}* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<int> ans;vector<int> postorderTraversal(TreeNode* root) {dfs(root);return ans;}void dfs(TreeNode* root){if(root == nullptr) return;dfs(root->left);dfs(root->right);ans.push_back(root->val);}
};
法二:迭代
Java
class Solution {public List<Integer> postorderTraversal(TreeNode root) {List<Integer> ans = new ArrayList<>();if(root == null) return ans;Stack<TreeNode> stk = new Stack<>();stk.push(root);while(!stk.isEmpty()){root = stk.pop();ans.add(root.val);if(root.left != null) stk.push(root.left);if(root.right != null) stk.push(root.right);}Collections.reverse(ans);return ans;}
}
C++
class Solution {
public:vector<int> postorderTraversal(TreeNode* root) {vector<int> ans;if(root == nullptr) return ans;stack<TreeNode*> stk;stk.push(root);while(!stk.empty()){root = stk.top();stk.pop();ans.push_back(root->val);if(root->left != nullptr) stk.push(root->left);if(root->right != nullptr) stk.push(root->right);}reverse(ans.begin(), ans.end());return ans;}
};
运行结果:

复杂度分析:
- 时间复杂度: O ( n ) O(n) O(n),其中
n是二叉树的节点数。每一个节点恰好被遍历一次。 - 空间复杂度: O ( n ) O(n) O(n),为递归或迭代过程中栈的开销,平均情况下为 O ( l o g n ) O(logn) O(logn),最坏情况下树呈现链状,为 O ( n ) O(n) O(n)。
题目来源:力扣。
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我 leetCode专栏,每日更新!
注: 如有不足,欢迎指正!
相关文章:
( “树” 之 前中后序遍历) 145. 二叉树的后序遍历 ——【Leetcode每日一题】
基础概念:前中后序遍历 1/ \2 3/ \ \ 4 5 6层次遍历顺序:[1 2 3 4 5 6]前序遍历顺序:[1 2 4 5 3 6]中序遍历顺序:[4 2 5 1 3 6]后序遍历顺序:[4 5 2 6 3 1] 层次遍历使用 BFS 实现,利用的就是 BFS…...
NPOI與Crystal report 13.0關於ICSharpCode.SharpZipLib控件版本衝突的解決方法
公司原來的系統用了Crystal report 13.0,它關聯使用ICSharpCode.SharpZipLib.dll (壓縮控件)的版本為0.85.1.271;後來因需要新增加 NPOI2.3控件,它關聯使用了ICSharpCode.SharpZipLib.dll 的版本為 高版本0.86…...
Sass @extend 与 继承
Sass extend 与 继承 extend 指令告诉 Sass 一个选择器的样式从另一选择器继承。 如果一个样式与另外一个样式几乎相同,只有少量的区别,则使用 extend 就显得很有用。 以下 Sass 实例中,我们创建了一个基本的按钮样式 .button-basic&#…...
权限控制导入到项目中
在项目中应用 进行认证和授权需要前面课程中提到的权限模型涉及的7张表支撑,因为用户信息、权限信息、菜单信息、角色信息、关联信息等都保存在这7张表中,也就是这些表中的数据是进行认证和授权的依据。所以在真正进行认证和授权之前需要对这些数据进行…...
CVPR2020:训练多视图三维点云配准
CVPR2020:训练多视图三维点云配准 Learning Multiview 3D Point Cloud Registration 源代码和预训练模型:https://github.com/zgojcic/3D_multiview_reg 论文地址: https://openaccess.thecvf.com/content_CVPR_2020/papers/Gojcic_Learn…...
string容器及其简单使用
string容器 概述声明和初始化获取字符串长度字符串拼接字符串比较字符串插入和删除字符串转换 概述 string是C中的一个标准库容器,用于处理字符串。它提供了一系列的操作函数,使得我们可以像处理其他容器一样方便地处理字符串。下面是string容器的详细介…...
芴甲氧羰酰基-氨基-聚乙二醇-巯基吡啶Fmoc-NH-PEG-OPSS
修饰性PEG芴甲氧羰基-氨基-聚乙二醇-巯基吡啶Fmoc-NH-PEG-OPSS是保护氨基的PEG衍生物之一 结构式: 芴甲氧羰酰基-氨基-聚乙二醇-巯基吡啶Fmoc-NH-PEG-OPSS聚乙二醇化可以提高聚乙二醇分子的稳定性,降低其免疫原性,仅用于科研实验。 FMOC-NH…...
【JavaWeb】Servlet(崔老师版)
文章目录 1.概述1.1 JavaWeb三大组件1.2 Servlet作用 2.ServletConfig接口3.Servlet接口3.1 实现Servlet的方式3.2 Servlet生命周期 4.HttpServlet抽象类5.ServletContext5.1 概述5.2 获取ServletContext5.3 JavaWeb四大域对象5.4 获取应用初始化参数5.5 ServletContext获取资源…...
ITSS服务经理 、服务工程师线上开班在即
为了促进企业信息技术服务-运行维护服务能力,全面系统的提升员工的IT服务知识和技能水平,且更好的满足参训企业的时间需求,我司将于5月份开展ITSS服务经理、服务工程师线上班。 日期和形式 五月份:ITSS服务项目经理:…...
【LeetCode】199.二叉树的右视图
1.问题 给定一个二叉树的 根节点 root,想象自己站在它的右侧,按照从顶部到底部的顺序,返回从右侧所能看到的节点值。 示例 1: 输入: [1,2,3,null,5,null,4] 输出: [1,3,4] 示例 2: 输入: [1,null,3] 输出: [1,3] 示例 3: 输入: [] 输出: []…...
Shell编程(三)grep sed awk文本处理三剑客
上一章: Shell编程(二)_做测试的喵酱的博客-CSDN博客 一、ps命令 指令: ps作用: 主要是查看服务器的进程信息选项含义: -e:等价于 ‘-A’ ,表示列出全部的进程 -f:显示全部的列&am…...
一步步带你学习Python编程:从零开始的查缺补漏
在快节奏的生活中,很难找到时间来学习新的技能。但有时候,我们会突然发现自己有一些空闲时间,而又不想虚度光阴。无聊的时候,我们可以选择学习一项新技能来充实自己。最近,我就因为有些无聊,决定重新学习Py…...
常见容器的方法
常见容器 向量 (vector)常用方法代码实例 列表 (list)常用方法 集合 (set)常用方法 映射 (map)方法 向量 (vector) 常用方法 vector::push_back(): 将元素插入向量尾部。 vector::pop_back(): 弹出向量尾部的元素。 vector::insert(): 在指定位置插入元素。 vector::erase():…...
【Linux】线程
1.理解地址空间和页表 1.地址空间是进程能够看到的资源窗口 2.页表决定进程真正拥有的资源情况 3.合理的对地址空间和页表进行资源划分就可以对一个进程的所有资源进行划分:过地址空间分为栈区、堆区…通过页表映射到不同的物理内存。 在32位平台下,…...
ASP.NET Core MVC 从入门到精通之wwwroot和客户端库
随着技术的发展,ASP.NET Core MVC也推出了好长时间,经过不断的版本更新迭代,已经越来越完善,本系列文章主要讲解ASP.NET Core MVC开发B/S系统过程中所涉及到的相关内容,适用于初学者,在校毕业生,…...
Oracle OCI 修改 Compute Instance Hostname
Oracle OCI 修改 Compute Instance Hostname Oracle Linux 7 及之后的版本 Oracle Linux 7 及之后的版本 1, Update the /etc/hostname file with below command. hostnamectl set-hostname <new name>2, Edit the oci configuration file for hostnames as given belo…...
垃圾收集算法面试总结
垃圾收集算法 标记 - 清除算法 首先标记出所有需要被回收的对象,标记完后统一回收所有被标记的对象。 后续的收集算法都是基于这种思路并对其不足进行改进而得到的。 这种方法主要有两个缺点: 一个是效率问题,标记和清除两个过程的效率都…...
grep替换指定字符串方法
在 Linux 命令行中,可以使用 grep 命令来查找匹配某个模式的字符串,并将其替换为另一个字符串。具体方法如下: grep -rl <pattern> <directory> | xargs sed -i s/<old_string>/<new_string>/g其中,<…...
主从模式、哨兵模式、集群模式(cluster)
主从模式、哨兵模式、集群模式(cluster) redis 实现高可用的方式分为 主从模式、哨兵模式、集群模式(cluster) 1. 主从模式(又称为主从复制) 表现为1个主节点,多个从节点,主节点负…...
题目3180:蓝桥杯2023年第十四届省赛真题-互质数的个数======及探讨互质专题
原题链接 https://www.dotcpp.com/oj/problem3162.html 想直接看题解的,跳转到第三次尝试即可。 已AC。 解析: (1)首先大家要知道什么叫互质: 以及它们的性质: 欧拉函数 在数论中,对正整…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
【人工智能】神经网络的优化器optimizer(二):Adagrad自适应学习率优化器
一.自适应梯度算法Adagrad概述 Adagrad(Adaptive Gradient Algorithm)是一种自适应学习率的优化算法,由Duchi等人在2011年提出。其核心思想是针对不同参数自动调整学习率,适合处理稀疏数据和不同参数梯度差异较大的场景。Adagrad通…...
多模态商品数据接口:融合图像、语音与文字的下一代商品详情体验
一、多模态商品数据接口的技术架构 (一)多模态数据融合引擎 跨模态语义对齐 通过Transformer架构实现图像、语音、文字的语义关联。例如,当用户上传一张“蓝色连衣裙”的图片时,接口可自动提取图像中的颜色(RGB值&…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
pikachu靶场通关笔记22-1 SQL注入05-1-insert注入(报错法)
目录 一、SQL注入 二、insert注入 三、报错型注入 四、updatexml函数 五、源码审计 六、insert渗透实战 1、渗透准备 2、获取数据库名database 3、获取表名table 4、获取列名column 5、获取字段 本系列为通过《pikachu靶场通关笔记》的SQL注入关卡(共10关࿰…...
重启Eureka集群中的节点,对已经注册的服务有什么影响
先看答案,如果正确地操作,重启Eureka集群中的节点,对已经注册的服务影响非常小,甚至可以做到无感知。 但如果操作不当,可能会引发短暂的服务发现问题。 下面我们从Eureka的核心工作原理来详细分析这个问题。 Eureka的…...
Windows安装Miniconda
一、下载 https://www.anaconda.com/download/success 二、安装 三、配置镜像源 Anaconda/Miniconda pip 配置清华镜像源_anaconda配置清华源-CSDN博客 四、常用操作命令 Anaconda/Miniconda 基本操作命令_miniconda创建环境命令-CSDN博客...
LCTF液晶可调谐滤波器在多光谱相机捕捉无人机目标检测中的作用
中达瑞和自2005年成立以来,一直在光谱成像领域深度钻研和发展,始终致力于研发高性能、高可靠性的光谱成像相机,为科研院校提供更优的产品和服务。在《低空背景下无人机目标的光谱特征研究及目标检测应用》这篇论文中提到中达瑞和 LCTF 作为多…...
如何在Windows本机安装Python并确保与Python.NET兼容
✅作者简介:2022年博客新星 第八。热爱国学的Java后端开发者,修心和技术同步精进。 🍎个人主页:Java Fans的博客 🍊个人信条:不迁怒,不贰过。小知识,大智慧。 💞当前专栏…...
