本文共 2508 字，大约阅读时间需要 8 分钟。
数据结构定义：
// 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 {
List result =new ArrayList<>();
public List postorderTraversal(TreeNode root) {
if(root == null)
return result;
if(root.left != null)
postorderTraversal(root.left);
if(root.right != null)
postorderTraversal(root.right);
result.add(root.val);
return result;
}
}
普通迭代：
class Solution {
public List postorderTraversal(TreeNode root) {
List result =new ArrayList<>();
if(root == null)
return result;
//pre的作用是记忆上一次遍历的节点，以便判断是否有右子树或右子树未遍历
TreeNode node = root,pre = null;
Stack stack =new Stack<>();
while(!stack.isEmpty() || node != null){
while(node != null){
stack.push(node);
node = node.left;
}
if((node=stack.peek()).right == null
|| node.right == pre){
pre = node;
result.add(stack.pop().val);
node =null;
}else{
pre = node;
node =node.right;
}
}
return result;
}
}
借鉴前序遍历思想：
//思路：
//前序遍历的过程是：(根-左-右)
//那么我们遍历的过程变为：(根-右-左)，最后的结果再进行下倒置
//顺序就变成了:(左-右-根),完成对后序的遍历
class Solution {
public List postorderTraversal(TreeNode root) {
List result =new ArrayList<>();
if(root == null){
return result;
}
Stack stack = new Stack<>();
TreeNode node =root;
while(!stack.isEmpty() || node != null){
while(node != null){
stack.push(node);
result.add(node.val);
node = node.right;
}
node = stack.pop().left;
}
Collections.reverse(result);
return result;
}
}
莫里斯遍历：
//还是借鉴前序遍历的思路，莫里斯遍历可参看我的中序遍历一文
class Solution {
public List postorderTraversal(TreeNode root) {
List result = new ArrayList<>();
if(root == null){
return result;
}
TreeNode node =root,pre = null;
while(node != null){
if(node.right == null){
result.add(node.val);
node =node.left;
}else{
pre = node.right;
while(pre.left != null && pre.left != node){
pre = pre.left;
}
if(pre.left == null){
pre.left = node;
result.add(node.val);
node = node.right;
}else{
pre.left = null;
node =node.left;
}
}
}
Collections.reverse(result);
return result;
}
借鉴头指针插入法:
class Solution {
public List postorderTraversal(TreeNode root) {
LinkedList result =new LinkedList<>();
LinkedList stack =new LinkedList<>();
if(root == null){
return result;
}
stack.addFirst(root);
while(!stack.isEmpty()){
TreeNode node =stack.removeFirst();
result.addFirst(node.val);
if(node.left != null){
stack.addFirst(node.left);
}
if(node.right != null){
stack.addFirst(node.right);
}
}
return result;
}
}
转载地址：http://mqvto.baihongyu.com/