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].
Note: Recursive solution is trivial, could you do it iteratively?

Solution：Stack

思路：
Time Complexity: O(N) Space Complexity: O(N)

Solution：Recursive

思路：
Time Complexity: O(N) Space Complexity: O(N)

Solution：Morris Traversal

思路：
Time Complexity: O(N) Space Complexity: O(1)

Solution Code：

Stack (regular)

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
       List<Integer> list = new ArrayList<>();
        if(root == null) return list;
        Deque<TreeNode> stack = new ArrayDeque<>();
        //Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            list.add(cur.val);
            if(cur.right != null) stack.push(cur.right);
            if(cur.left != null) stack.push(cur.left);
        }
        return list;
    }
}

Stack (only right children are stored to the stack)

class Solution {
    public List<Integer> preorderTraversal(TreeNode node) {
       List<Integer> list = new LinkedList<Integer>();
        Deque<TreeNode> rights = new ArrayDeque<TreeNode>();
        while(node != null) {
            list.add(node.val);
            if (node.right != null) {
                rights.push(node.right);
            }
            node = node.left;
            if (node == null && !rights.isEmpty()) {
                node = rights.pop();
            }
        }
        return list;
    }
}

Recursive:

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> list = new LinkedList<Integer>();
        preHelper(root,pre);
        return pre;
    }
    public void preHelper(TreeNode root, List<Integer> list) {
        if(root==null) return;
        list.add(root.val);
        preHelper(root.left, list);
        preHelper(root.right, list);
    }
}