145 Binary Tree Postorder Traversal 二叉树的后序遍历
2024-09-06 15:55:00
给定一棵二叉树,返回其节点值的后序遍历。
例如:
给定二叉树 [1,null,2,3],
1
\
2
/
3
返回 [3,2,1]。
注意: 递归方法很简单,你可以使用迭代方法来解决吗?
详见:https://leetcode.com/problems/binary-tree-postorder-traversal/description/
Java实现:
递归实现:
/**
* 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;
}
return postorderTraversal(root,res);
}
private List<Integer> postorderTraversal(TreeNode root,List<Integer> res){
if(root==null){
return res;
}
postorderTraversal(root.left,res);
postorderTraversal(root.right,res);
res.add(root.val);
return res;
}
}
非递归实现:
/**
* 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> stk1=new Stack<TreeNode>();
Stack<TreeNode> stk2=new Stack<TreeNode>();
stk1.push(root);
while(!stk1.isEmpty()){
root=stk1.pop();
stk2.push(root);
if(root.left!=null){
stk1.push(root.left);
}
if(root.right!=null){
stk1.push(root.right);
}
}
while(!stk2.isEmpty()){
res.add(stk2.pop().val);
}
return res;
}
}
最新文章
- [每日Linux]Linux下xsell和xftp的使用
- C#不对称加密
- js的encodeURIComponent与java的URLEncoder的区别
- rem自适应布局的回顾总结
- Todd&#39;s Matlab讲义第4讲:控制误差和条件语句
- C/C++中调用python文件
- Python之路-python(面向对象一)
- ZooKeeper是什么?
- Java I/O---File类
- CentOS 6.*通过yum安装 MySQL-5.5
- Ubuntu安装telent服务器时出现:apt-get:Package has no installation
- RTMPdump(libRTMP) 源代码分析 10: 处理各种消息(Message)
- 学习 JavaScript (三)核心概念:语法、变量、数据类型
- CSS中的opacity,不透明度的坑
- 面试北京XX科技总结
- Javascript高级编程学习笔记(24)—— 函数表达式(2)闭包
- easyui+themeleaf 分页查询实现
- 同步对象(同步条件Event)
- Shiro:ajax的session超时处理
- scp ssh: connect to host 9.123.159.41 port 22:connection refused的解决办法
热门文章
- Hibernate exception
- sql语句,无法绑定由多个部分组成的标识符 ";xxx";
- web中使用svg失量图形及ie8以下浏览器的处理方式
- DataSnap Mobile Client Tutorial
- 没有该栏目数据可能缓存文件(data/cache/inc_catalog_base.inc)没有更新请检查是否有写入权限
- html5--6-3 CSS语法2
- codeforces 667A A. Pouring Rain(水题)
- Spring中Bean获取IOC容器服务的方法
- 替换一个文件中的内容BAT
- jqGrid 编辑完数据后能返回到当前位置的方法