二叉树非递归的前，中，后序遍历的思考

三种遍历方式的根本区别是

1. Preorder: print parent directly.
2. Inorder: print parent when return from left child.
3. Postorder: print parent when return from right child.

可以用堆栈实现非递归遍历

而用堆栈实现又有两种方式

1.堆栈中存放的是未访问过的结点，这种方式先让根进栈，只要栈不为空，就可以做弹出操作，  每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。  

2.堆栈中存放的是访问过的结点，就是按照人脑中模拟遍历二叉树的方式确定访问节点的时机，比如先序是遇到即访问。

后序遍历模板

常用的：

public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        Stack<TreeNode> st=new Stack<TreeNode>();
        if(root==null) return list;
        TreeNode pre=null;
        TreeNode cur=root;
        while(!st.isEmpty()||cur!=null){
        while(cur!=null){
        st.push(cur);
        cur=cur.left;
        }
        cur=st.peek();
        if(cur.right==null||cur.right==pre){
        list.add(cur.val);
        pre=cur;
        st.pop();
        cur=null;
        }
        else{
        cur=cur.right;
        }
        }
        return list;
    }

不太常用的

List<Integer> res = new ArrayList<>();
        if (root == null) return res;

        Stack<TreeNode> stack = new Stack<>();
        stack.add(root);

        while (!stack.isEmpty()) {
            TreeNode node = stack.peek();
            if (node.right != null)
                stack.add(node.right);

            if (node.left != null)
                stack.add(node.left);

            if (node.left == null && node.right == null) {
                node = stack.pop();
                res.add(node.val);
                while (!stack.isEmpty() && // isParent?
                        (stack.peek().right == node || stack.peek().left == node)) {
                    // right child can be null, if stack.peek().left == node, then return from it.
                    node = stack.pop();
                    res.add(node.val);
                }
            }
        }

        return res;