Binary Tree Postorder Traversal

• 描述
  Given a binary tree, return the postorder traversal of its nodes’ values. For example: Given binary tree
  {1, #, 2, 3}, return [2, 3, 1].

Note: Recursive solution is trivial, could you do it iteratively?

• 回溯思想，有右子树的节点应访问两次，如果节点第一次弹栈，即第一次访问，为该节点打上标记，表示我已经被访问过了，并重新压栈，待遍历完右子树，第二次弹栈，那么就知道此节点左子树和右子树均被访问过，那么此节点可以被加入结果集，应注意节点重新压栈后避免其右子树再次入栈。

• 时间复杂度O(n)，空间复杂度O(n)

import java.util.*;

public class Solution {
    public List<Integer> postorderTraverse(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if (root == null)
            return result;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode p = root;
        Map<TreeNode, Boolean> map = new HashMap<>();
        while (!stack.isEmpty() || p != null) {
            if (p != null) {
                // 右子树已被压栈一次
                if (map.containsKey(p)) {
                    p = null;
                    continue;
                }
                stack.push(p);
                if (!map.containsKey(p))
                    map.put(p, false);
                p = p.left;
            } else {
                p = stack.pop();
                // 有右子树的节点弹出且已被访问一次，直接输出
                if ((map.get(p) == true && p.right != null) || p.right == null) {
                    result.add(p.val);
                }
                // 包含右子树的节点，第一次弹栈后，不输出，而再次入栈，确保右子树访问完，能第二次访问该节点
                if (p.right != null && map.containsKey(p) && map.get(p) == false) {
                    stack.push(p);
                    map.put(p, true);
                }
                p = p.right;
            }
        }
        return result;
    }
}