NonRecursiveTraversal of BinaryTree (preorder, inorder and postorder) @LeetCode

Like title claims. Non Recursive way.

	package leetcode.tree;
	import java.util.ArrayList;
	import java.util.Stack;
	/**
	* @author jeffwan
	* @date Feb 9, 2014
	*
	* NonRecursiveTraversal
	* inorder and preorder are almost same, postorder is a little complicated
	* All use one stack, and postorder use another TreeNode head as parent pointer.
	*
	*/
	public class NonRecursiveTraversal {
	public ArrayList<Integer> preorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode node = root;
	while ( node != null || stack.size() > 0) {
	while (node != null) {
	stack.push(node);
	list.add(node.val);
	node = node.left;
	}
	if (stack.size() > 0) {
	node = stack.pop();
	node = node.right;
	}
	}
	return list;
	}
	public ArrayList<Integer> inorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	TreeNode node = root;
	while (node != null || stack.size() > 0) {
	while(node != null) {
	stack.push(node);
	node = node.left;
	}
	if (stack.size() > 0) {
	node = stack.pop();
	list.add(node.val);
	node = node.right;
	}
	}
	return list;
	}
	/**
	* @date Feb 9, 2014
	*
	* Take Care: Different from Inorder and Preorder, postOrder will push root at first.
	* And then call next.left, we need to make sure it is not null. inorder and preorder, traversal already handle that.
	*
	* Could stack push a null value? -- Yes, stack will be [null]
	*
	* Pop condition:
	* next.left == null && next.right == null, which means it's leaf
	* parent will be push at the bottom of stack --> PostOrder. and then right child.
	*
	* next.left == head, next.right == head ---> check if next(stack peek) is the parent, also could be right child
	*/
	public ArrayList<Integer> postorderTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	Stack<TreeNode> stack = new Stack<TreeNode>();
	stack.push(root);
	TreeNode popped = root;
	if (root == null) {
	return list;
	}
	while (!stack.isEmpty()) {
	TreeNode next = stack.peek();
	if (next.left == popped || next.right == popped
	|| (next.left == null && next.right == null)) {
	next = stack.pop();
	list.add(next);
	popped = next;
	} else {
	if (next.right != null) {
	stack.push(next.right);
	}
	if (next.left != null) {
	stack.push(next.left);
	}
	}
	}
	return list;
	}
	/**************************** Recursive Way **************************/
	public ArrayList<Integer> preorderRecursiveTraversal(TreeNode root) {
	ArrayList<Integer> list = new ArrayList<Integer>();
	traversal(list, root);
	return list;
	}
	public void traversal(ArrayList<Integer> list, TreeNode node) {
	if (node == null) {
	return;
	}
	list.add(node.val);
	traversal(list, node.left);
	traversal(list, node.right);
	}
	private class TreeNode {
	int val;
	TreeNode left;
	TreeNode right;
	TreeNode(int x) {val = x; };
	}
	}

view raw NonRecursiveTraversal.java hosted with ❤ by GitHub