二叉树的后序遍历是比较常见的一种访问方式，它是通过左---右---根的顺序访问树的，

了解并掌握树的后序遍历是很有必要的，也是学习算法的基础，这里分别给出递归算法和非递归算法，

递归算法很简单，非递归稍微复杂，它比中序和前序更难一点，这里关系到节点重复入栈，

理解非递归的重要的一点就是：永远从最左开始遍历，如果存在右节点，此时要判断右节点是继续入栈还是略过，

这里通过visitor来标记右节点是否已经入过栈，如果入过，标记为1，下一次判断时不再入栈，直接输出当前节点即可。这里使用了标记的方式来避免重复入栈，但我想应该可以无需借助标记方式，这个应该更复杂，朋友们如果有更好的非递归算法可以在评论区分享出来哦

以下下图为例，输出后序遍历

预期的结果为： 4, 8, 6, 12, 16, 14, 10

递归和非递归代码如下：

import java.util.ArrayList;import java.util.List;import java.util.Stack;/** * 后序遍历的非递归和递归的实现 *  * @author ssj * */public class AfterList {	public static void main(String[] args) {		// 创建一颗二叉树		TreeNode root = new TreeNode("10");		TreeNode n6 = new TreeNode("6");		TreeNode n14 = new TreeNode("14");		n6.setParent(root);		n14.setParent(root);		root.setLeft(n6);		root.setRight(n14);		TreeNode n4 = new TreeNode("4");		TreeNode n8 = new TreeNode("8");		n6.setLeft(n4);		n6.setRight(n8);		TreeNode n12 = new TreeNode("12");		TreeNode n16 = new TreeNode("16");		n14.setLeft(n12);		n14.setRight(n16);		System.out.println("---------递归遍历结果--------------------");		List list = new ArrayList();		afterListDiGui(root, list);		System.out.println(list);						System.out.println("---------非递归遍历结果--------------------");		List list2 = afterList(root);		System.out.println(list2);	}	/**	 * 递归后序遍历	 * 	 * @param root	 * @return	 */	public static void afterListDiGui(TreeNode root, List list) {		if (root == null) {			return;		}		afterListDiGui(root.left, list);		afterListDiGui(root.right, list);		list.add(root.name);	}	/**	 * 非递归后序遍历	 * 	 * @param root	 * @return	 */	public static List afterList(TreeNode root) {		Stack<TreeNode> sk = new Stack<TreeNode>();		List list = new ArrayList();		TreeNode n = root;		while (n != null) {			// 从当前节点开始，一直往左方向前进			while (n != null) {				sk.push(n);								n = n.left;			}			// 取出入栈的右节点			while (!sk.empty()) {				TreeNode n2 = sk.pop();												if (n2.right == null||n2.right.visitor) {					//不存在右节点或者右节点已经访问过了，则右节点无需再关心					list.add(n2.getName());					n2.visitor=true;				}else {					//存在右孩子未被访问，当前节点退回到栈中，先处理右孩子相关的节点					sk.push(n2);					n=n2.right;//继续上面的轮回					break;				}							}		}		return list;	}}/** * 树节点 * @author ssj * */class TreeNode {	public String name;	public TreeNode left;	public TreeNode right;	public TreeNode parent = null;	public boolean visitor=false;//标记该节点是否访问过	public String getName() {		return name;	}	public void setName(String name) {		this.name = name;	}	public TreeNode getParent() {		return parent;	}	public void setParent(TreeNode parent) {		this.parent = parent;	}	public TreeNode(String name) {		super();		this.name = name;	}	public TreeNode getLeft() {		return left;	}	public void setLeft(TreeNode left) {		this.left = left;	}	public TreeNode getRight() {		return right;	}	public void setRight(TreeNode right) {		this.right = right;	}}

运行结果：