144. Binary Tree Preorder Traversal

The basic idea of preoder traversal is the same to inorder traversal 94. Binary Tree Inorder Traversal, i.e., use stack to save node under process. The difference is:

1. Inorder: we add node to result list when node is popped out of the stack;
2. Preorder: we add node to result list when node is pushed into the stack.

public List<Integer> preorderTraversal(TreeNode root) {
    List<Integer> resultList = new ArrayList<Integer>();
    Stack<TreeNode> stack = new Stack<TreeNode>();
    TreeNode current = root;
    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            resultList.add(current.val);
            stack.push(current);
            current = current.left;
        }
        current = stack.pop().right;
    }
    return resultList;
}