145. 二叉树的后序遍历
给定一个二叉树，返回它的 后序 遍历。

示例:

输入: [1,null,2,3]  
   1
    \
     2
    /
   3 

输出: [3,2,1]
进阶: 递归算法很简单，你可以通过迭代算法完成吗？

解析

首先压入根节点，然后一直循环压入左子节点，然后如果没有右子节点或者右子节点已经访问过了就访问父亲节点。

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        if (root == null) return new ArrayList<Integer>();

        TreeNode node = root;
        List<Integer> ret = new ArrayList<Integer>();

        Stack<TreeNode> stack = new Stack<TreeNode>();
        while(node != null || !stack.isEmpty()) {
            while (node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            // 后序遍历
            // 如果没有右孩子或者右孩子被访问过了
            if (node.right == null ||
                    (ret.size() != 0 && ret.get(ret.size() - 1).equals(node.right.val)) ) {
                ret.add(node.val);
                node = null;
            }  else {
                stack.push(node);
                node = node.right;
            }
        }
        return ret;
    }
}

注意：本文归作者所有，未经作者允许，不得转载