Java iterative clean solution (3 ms)


  • 0
    D
    public class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        if (root == null) {
            return list;
        }
        HashMap<TreeNode,Boolean> nodesPushedToStack = new HashMap<TreeNode,Boolean>();
        Stack<TreeNode> stack = new Stack<TreeNode>();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (!nodesPushedToStack.containsKey(node)) {
                  nodesPushedToStack.put(node,true); 
                  stack.push(node);
                  if (node.right != null) {
                      stack.push(node.right);
                  }
                  if (node.left != null) {
                      stack.push(node.left);
                  }
            } 
            else {
                list.add(node.val);
            }
        }
        return list;
    }
    

    }

    The idea is to check whether the current node has already been pulled out of the stack thus its sons as already been taken care of or it is the first time we encounter it so we need to push it to the stack and then push its sons.
    A hash map is perfect for this to check if a node has been already pushed once.


  • 0
    J

    This is a great solution! Perhaps I would use a set instead of a map in this situation?


  • 0
    D

    If I'm not wrong, Hash set is slower than hash map, I'm not sure why.
    Hashset is more readable and clean, so maybe it is better in some cases.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.