Reference:
http://leetcode.com/2010/04/binary-search-tree-in-order-traversal.html
http://leetcode.com/2010/10/binary-tree-post-order-traversal.html

The preorder uses an arraylist and a stack (via LinkedList). It first pushes the root into the stack; then pops up the top of the stack (root here), adds that to the arraylist, pushes its right child and then left child into the stack; then pops the leftmost child so far, adds it to the arraylist, pushes its right child and then left child into the stack; then …

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack1 = new LinkedList<TreeNode>();
        ArrayList<Integer> ret = new ArrayList<Integer>();
        if(root != null)
                stack1.push(root);
        while(stack1.size() != 0) {
                TreeNode top = stack1.pop();
                ret.add(top.val);
                        
                if(top.right != null)
                        stack1.push(top.right);
                if(top.left != null)
                        stack1.push(top.left);
        }
                
        
        return ret;
    }
}

The post-order adds another stack to reverse the first stack, and then adds them to the arraylist.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> postorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack1, stack2;
        stack1 = new LinkedList<TreeNode>();
        stack2 = new LinkedList<TreeNode>();
		if(root != null)
			stack1.push(root);
		while(stack1.size() != 0) {
				TreeNode top = stack1.pop();
				stack2.push(top);
				if(top.left != null)
					stack1.push(top.left);
				if(top.right != null)
					stack1.push(top.right);
		}
		ArrayList<Integer> ret = new ArrayList<Integer>();
		while(stack2.size() != 0) {
				ret.add(stack2.pop().val);
		}
		return ret;
    }
}

In-order traversal could be solved using an arraylist and a stack too. We will not stop push left value until we reach a null. We then backtrack and pop a value (the first popped value is the left-most leaf). And then start traverse its right child. And then start the above process again.
Test case:
[]
[1]
[1, #, 2]

confused what "{1,#,2,3}" means? > read more on how binary tree is serialized on OJ.

OJ’s Binary Tree Serialization:

The serialization of a binary tree follows a level order traversal, where ‘#’ signifies a path terminator where no node exists below.

Here’s an example:

   1
  / \
 2   3
    /
   4
    \
     5

The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList<TreeNode>();
        ArrayList<Integer> ret = new ArrayList<Integer>();
        TreeNode current = root;
        
        boolean done = false;
        while(true) {
            if(current != null) {
                stack.push(current);
                current = current.left;
            } else {
                if(stack.size() == 0)
                    break;
                else {
                   current = stack.pop();
                   ret.add(current.val);
                   current = current.right; 
                }
                
            }
            
            
        }
        return ret;
    }
}
Advertisements