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; } }