Binary Tree Inorder Traversal

Given a binary tree, return the inorder traversal of its nodes' values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,3,2].

Note: Recursive solution is trivial, could you do it iteratively?

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

Solution:
Basic recursion.
In order: left-root-right.
To do it iteratively, we can make use of a stack. Keeping push nodes, once the top element in stack has a left child, don't pop it out and continue to push its left child.
Wait, when we pop out an element, are we going to do so? it will cause infinite loop. So we need to mark nodes which we have been visited.
Alternatively, use a pointer cur (current) can avoid this.

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ArrayList inorderTraversal(TreeNode root) {
        ArrayList ret = new ArrayList();
        Stack stack = new Stack();
        
        if(root == null) return ret;
        TreeNode cur = root;
        
        while(!stack.isEmpty() || cur != null){
            if(cur != null){    // keep pushing left children into stack.
                stack.push(cur);
                cur = cur.left;
            }
            else{                            
                TreeNode top = stack.pop();
                ret.add(top.val);  // pop out an element, and go to its right child
                cur = top.right;
            }
        }
        return ret;
    }
}