Java实现 LeetCode 145 二叉树的后序遍历
2024-10-09 03:15:07
145. 二叉树的后序遍历
给定一个二叉树,返回它的 后序 遍历。
示例:
输入: [1,null,2,3]
1
\
2
/
3
输出: [3,2,1]
进阶: 递归算法很简单,你可以通过迭代算法完成吗?
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {//非递归写法
List<Integer> res = new ArrayList<Integer>();
if(root == null)
return res;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode pre = null;
stack.push(root);
while(!stack.isEmpty()){
TreeNode curr = stack.peek();
if((curr.left == null && curr.right == null) ||
(pre != null && (pre == curr.left || pre == curr.right))){
//如果当前结点左右子节点为空或上一个访问的结点为当前结点的子节点时,当前结点出栈
res.add(curr.val);
pre = curr;
stack.pop();
}else{
if(curr.right != null) stack.push(curr.right); //先将右结点压栈
if(curr.left != null) stack.push(curr.left); //再将左结点入栈
}
}
return res;
}
}
最新文章
- tp中session用来做权限方法 (缓解mysql压力)
- PHP中include和require(转)
- Top 10 Universities for Artificial Intelligence
- font-family属性与字体对齐
- spinner中的onNothingSelected方法到底什么时候调用?
- sqlserver高版本到低版本迁移
- 用C语言制作小型商品信息管理系统过程中的问题
- 深入分析MFC文档视图结构(项目实践)
- openstack trove,使pylint忽略错误
- 无法打开登录 &#39;ASPState&#39; 中请求的数据库。登录失败。
- Java核心技术(Java白皮书)卷Ⅰ 第一章 Java程序设计概述
- Multi-View 3D Reconstruction with Geometry and Shading——Part-1
- python Django2.X,报错 ‘learning_logs ’is not a registered namespace,如何解决?
- Py之any函数【转载】
- SQL Server-常用分页语句
- loj 10181 绿色通道 二分答案+单调队列DP
- abp ef codefirst Value cannot be null. Parameter name: connectionString
- 5个经典的javascript面试问题
- 用@resource注解方式完成属性装配
- 【BZOJ4922】[Lydsy六月月赛]Karp-de-Chant Number 贪心+动态规划
热门文章
- CF-612D The Union of k-Segments 差分
- 实验三 UML建模工具的安装与使用
- SQL注入和Mybatis预编译防止SQL注入
- MySQL数据库基础操作语句
- fastDFS多线程并发执行出现的问题
- mysql设置文档快捷写
- NPOI导入excel为datatable (xls xlsx xlsm)
- 关于Slow HTTP Denial of Service Attack slowhttptest的几种慢攻击DOS原理
- Java并发包5--同步工具CountDownLatch、CyclicBarrier、Semaphore的实现原理解析
- E. Alternating Tree 树点分治|树形DP