# 二叉树的后序遍历 - 非递归版java实现

## 二叉树的后序遍历

### 版本一

``````
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
/* 用来记录最新出栈的节点， * 如果当前节点的右儿子与flag相同，说明当前节点右子树已完成遍历 */
TreeNode flag = null;
ArrayList<Integer> ans = new ArrayList<Integer>(20);
while (cur != null) {
stack.push(cur);
cur = cur.left;
}
while (!stack.isEmpty()) {
cur = stack.pop();
if (cur.right == null || cur.right == flag) {
flag = cur;
}
else {
stack.push(cur);
cur = cur.right;
while(cur != null) {
stack.push(cur);
cur = cur.left;
}
}
}
return ans;
}
}``````

#### 版本二

``````
import java.util.ArrayList;
import java.util.Stack;
public class Solution {
public ArrayList<Integer> postorderTraversal(TreeNode root) {
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode cur = root;
TreeNode prior = null;
ArrayList<Integer> ans = new ArrayList<Integer>(20);
while (cur != null || !stack.isEmpty()) {
if (cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
if (cur.right == null || cur.right == prior) {
prior = cur;
cur = null;
}
else {
stack.push(cur);
cur = cur.right;
stack.push(cur);
cur = cur.left;
}
}
}
return ans;
}
}``````

#### TreeNode的定义

``````    public class TreeNode {
int val;
TreeNode left;
TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
``````
原文作者：cwwang15
原文地址: https://blog.csdn.net/WANG_Chaunwang/article/details/79896631
本文转自网络文章，转载此文章仅为分享知识，如有侵权，请联系博主进行删除。