Binary Tree Postorder Traversal

题目

Given a binary tree, return the postorder traversal of its nodes' values.

For example:

Given binary tree {1,#,2,3},
   1
    \
     2
    /
   3
return [3,2,1].

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

答案

class Solution {

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> stk = new Stack<>();
        Map<TreeNode, Boolean> map = new HashMap<>();

        pushLeft(stk, map, root);

        while(!stk.isEmpty()) {
            TreeNode curr = stk.peek();
            Boolean is_right_visited = map.get(curr);
            if(is_right_visited) {
                list.add(stk.pop().val);
            }
            else {
                if(curr.right != null) {
                    pushLeft(stk, map, curr.right);
                }
                map.put(curr, true);
            }
        }
        return list;
    }

    public void pushLeft(Stack<TreeNode> stk, Map<TreeNode, Boolean> map, TreeNode root) {
        while(root != null) {
            stk.push(root);
            map.put(root, false);
            root = root.left;
        }
    }   
}