Binary Tree Postorder Traversal (Java)

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?

Solution;

For iterative solution, we know postal order is visit children before parent so  a stack could be apply here as a helper structure. Then, we can ' push left child from root until left most leaf into stack. then start pop node  from the stack, however, if the current node which going to be pop out has right node we should start push all left nodes of the right child until to leaf. But the trick point is how to tell if the mid need to be pop out  , We can use a child node to catch every popped out  node, then if the mid's right node equal to child node which mean this mid's right node has been visited, it is a good time to pop out the mid one .

	/*
	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].
	*/
	/**
	* Definition for binary tree
	* public class TreeNode {
	* int val;
	* TreeNode left;
	* TreeNode right;
	* TreeNode(int x) { val = x; }
	* }
	*/
	// iterative solution 9/14/2014
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	ArrayList<Integer> result = new ArrayList<Integer>();
	if (root == null){
	return result;
	}
	Stack<TreeNode> stack =new Stack<TreeNode> ();
	LinkedList<TreeNode> visitedList= new LinkedList<TreeNode> ();
	while(root!=null){
	stack.push(root);
	root=root.left;
	}
	while(!stack.isEmpty()){
	TreeNode current = stack.peek();
	if (current.right == null || visitedList.contains(current)){
	result.add(current.val);
	stack.pop();
	if (visitedList.contains(current)){
	visitedList.remove(current);
	}
	}
	else{
	visitedList.add(current);
	root=current.right;
	while (root!=null){
	stack.push(root);
	root=root.left;
	}
	}
	}
	return result;
	}
	}
	// Iterative Solution
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> result=new ArrayList<Integer>();
	if (root==null){
	return result;
	}
	Stack<TreeNode> stack=new Stack<TreeNode>();
	TreeNode runner=root;
	while (runner!=null){
	stack.push(runner);
	runner=runner.left;
	}
	// child node used to record if mid node's child has been visited inorder to tell if need to pop out
	//the mid node
	TreeNode child=null;
	while (!stack.isEmpty()){
	TreeNode current=stack.peek();
	if (current.right==null || current.right==child){
	result.add(stack.pop().val);
	// catch the child node, inorder mid node could check if its child already be visited
	child=current;
	}
	else{
	current=current.right;
	while (current!=null){
	stack.push(current);
	current=current.left;
	}
	}
	}
	return result;
	}
	}
	public class Solution {
	public List<Integer> postorderTraversal(TreeNode root) {
	List<Integer> result=new ArrayList<Integer> ();
	if (root==null){
	return result;
	}
	buildResult(root, result);
	return result;
	}
	private void buildResult(TreeNode root, List<Integer> result){
	if (root==null){
	return;
	}
	buildResult(root.left, result);
	buildResult(root.right, result);
	result.add(root.val);
	}
	}

view raw BinaryTreePostorderTrave.java hosted with ❤ by GitHub