Clear java solution using Stack and Set,


  • 0
    L

    Use a stack and a hashset [O(N) space], so not pretty efficient but clear.

    public ArrayList<Integer> postorderTraversal3(TreeNode root) {
        	ArrayList<Integer> out = new ArrayList<Integer>();
            if (root == null){
                return out;
            }
        	Stack<TreeNode> stack = new Stack<TreeNode>();
        	Set<TreeNode> set = new HashSet<TreeNode>();
        	stack.push(root);
        	while (!stack.isEmpty()){
        		TreeNode t = stack.peek();
        		if (!set.contains(t.left) && t.left != null){            //if a unvisited left subbranch exists
        			stack.push(t.left);
        			continue;
        		} else if (!set.contains(t.right) && t.right != null) {  //if a unvisited right subbranch exists
        			stack.push(t.right);
        			continue;
        		} else {
        			set.add(t);
        			out.add(stack.pop().val);            //output
        			continue;
        		}
        	}
        	return out;
        }

Log in to reply
 

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