LeetCode - Binary Tree Preorder Traversal | Darren's Blog

http://www.programcreek.com/2012/12/leetcode-solution-for-binary-tree-preorder-traversal-in-java/
Given a binary tree, return the preorder traversal of its nodes' values.
Morris Traversal:O(1) space

public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        TreeNode p = root, q = null;

        while (p != null) {

            if (p.left == null) {   // Empty left subtree

                result.add(p.val);  // Access the value of current node

                p = p.right;

            } else {

                // Find in-order predecessor of current node

                q = p.left;

                while (q.right != null && q.right != p)

                    q = q.right;

                if (q.right == null) {  // Its left subtree has not been traversed; link it to its predecessor

                    q.right = p;

                    result.add(p.val);  // Access the value of current node

                    p = p.left;

                } else {    // Its left subtree has been traversed; recover tree structure

                    q.right = null;

                    p = p.right;

                }

            }

        }

        return result;

    }

Iterative: Using Stack
1) Create an empty stack nodeStack and push root node to stack.
2) Do following while nodeStack is not empty.
….a) Pop an item from stack and print it.
….b) Push right child of popped item to stack
….c) Push left child of popped item to stack

void iterativePreorder(node *root)

{

    if (root == NULL)

       return;

    // Create an empty stack and push root to it

    stack<node *> nodeStack;

    nodeStack.push(root);

    /* Pop all items one by one. Do following for every popped item

       a) print it

       b) push its right child

       c) push its left child

    Note that right child is pushed first so that left is processed first */

    while (nodeStack.empty() == false)

    {

        // Pop the top item from stack and print it

        struct node *node = nodeStack.top();

        printf ("%d ", node->data);

        nodeStack.pop();

        // Push right and left children of the popped node to stack

        if (node->right)

            nodeStack.push(node->right);

        if (node->left)

            nodeStack.push(node->left);

    }

}

public ArrayList<Integer> preorderTraversal(TreeNode root) {

        ArrayList<Integer> result = new ArrayList<Integer>();

        if (root == null)

            return result;

        Deque<TreeNode> stack = new ArrayDeque<TreeNode>();     // Used to restore parents

        TreeNode p = root;

        while (p != null || !stack.isEmpty()) {

            if (p != null) {    // Whenever we meet a node, push it into the stack and go to its left subtree

                stack.push(p);

                result.add(p.val);

                p = p.left;

            } else {    // Left subtree has been traversed, add the value of current node, and go to its right subtree

                p = stack.pop();

                p = p.right;

            }

        }

        return result;

    }

Recursive

private void recursivePreorderTraversal(TreeNode root, ArrayList<Integer> result) {

        if (root == null)

            return;

        result.add(root.val); 

        recursivePreorderTraversal(root.left, result); 

        recursivePreorderTraversal(root.right, result);

    }

Also check http://massivealgorithms.blogspot.com/2014/09/tree-traversal.html
Java: http://www.programcreek.com/2012/12/leetcode-solution-for-binary-tree-preorder-traversal-in-java/

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

http://blog.csdn.net/linhuanmars/article/details/21428647

public ArrayList<Integer> preorderTraversal(TreeNode root) {
    ArrayList<Integer> res = new ArrayList<Integer>();
    if(root == null)
        return res;
    LinkedList<TreeNode> stack = new LinkedList<TreeNode>();//Use linkedlist as stack
    while(root!=null || !stack.isEmpty())
    {
        if(root!=null)
        {
            stack.push(root);
            res.add(root.val);
            root = root.left;
        }
        else
        {
            root = stack.pop();
            root = root.right;
        }
    }
    return res;
}

Read full article from LeetCode - Binary Tree Preorder Traversal | Darren's Blog