post Order traversal

public class Solution{
	class TreeNode{
		int val;
		TreeNode left, right;
		public TreeNode(int val){
			this.val = val;
			this.left = null;
			this.right = null;
		}
	}

//https://blog.csdn.net/zhangxiangDavaid/article/details/37115355 

	/*
		father->left son->right son

	*/
	//recursion
	public List<Integer> postOrderTraversal(TreeNode root){
		List<Integer> res = new ArrayList<>();

		if (root == null) {
			return 
		}

		res.addAll(postOrderTraversal(root.left));
		res.addAll(postOrderTraversal(root.right));
		res.add(root.val);
		return res;
	}
	//non-recursion
	/*
		我们使用prev变量跟踪上一次访问的节点。假设栈顶元素是curr。当prev是curr的父节点时，我们正在向下遍历树。\
		此时，优先遍历curr的左孩子（将左孩子压入栈）。如果没有左孩子，再看右孩子。如果左右孩子都不存在（curr是叶节点），
		就输出curr的值并弹出栈顶元素。如果prev是curr的左孩子，我们正在从左子树向上遍历。我们看一下curr的右孩子。如果可以，
		就从右孩子向下遍历（将右孩子压入栈），否则打印curr的值并弹出栈顶元素。如果prev是curr的右孩子，
		我们正在从右子树向上遍历。打印curr的值并弹出栈顶元素。
	*/
	public List<Integer> postOrderTraversal(TreeNode root){
		List<Integer> res = new ArrayList<>();
		Stack<Integer> stack = new Stack<>();
		TreeNode pre = null;
		TreeNode cur = root;
		if (root == null) {
			return res;
		}
		stack.push(root);

		while(!stack.isEmpty()){
			cur =stack.peek();
			//traversal down
			if (pre == null || pre.left == cur || pre.right == cur) {
				if (cur.left != null) {
					stack.push(cur.left);
				}

				else if (cur.right != null) {
					stack.push(cur.right);
				}
			}

			//traversal up
			else if (cur.left == pre) {
				if (cur.right != null) {
					stack.push(cur.right);
				}
			}else{
				res.add(cur.val);
				stack.pop();
			}

			pre = cur;
		}

	}
}