Binary Tree Preorder Traversal

Question

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

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

  1
    \
     2
    /
   3

return [1,2,3].

Solution : Recursive

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        preorder(root,result);
        return result;
    }

    public void preorder(TreeNode root, List<Integer> list){
        if(root==null) return;
        list.add(root.val);
        preorder(root.left, list);
        preorder(root.right, list);
    }
}

Solution : Iterative I

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        if(root==null) return result;
        LinkedList<TreeNode> stack=new LinkedList<TreeNode>();
        stack.push(root);
        while(!stack.empty()){
            TreeNode tmp=stack.pop();
            result.add(tmp.val);
            if(tmp.right!=null) stack.push(tmp.right);
            if(tmp.left!=null) stack.push(tmp.left);
        }
        return result;
    }
}

Solution : Iterative II

public class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> result=new ArrayList<Integer>();
        if(root==null) return result;
        LinkedList<TreeNode> stack=new LinkedList<TreeNode>();
        TreeNode pointer=root;
        while(pointer!=null || !stack.isEmpty()){
            while(pointer!=null){
                result.add(pointer.val);
                stack.push(pointer);
                pointer=pointer.left;
            }
            pointer=stack.pop().right;
        }
        return result;
    }
}