/**
 * public class TreeNode {
 *   public int key;
 *   public TreeNode left;
 *   public TreeNode right;
 *   public TreeNode(int key) {
 *     this.key = key;
 *   }
 * }
 */
public class Solution {
  //recursion:
  // public List<Integer> preOrder(TreeNode root) {
  //   // Write your solution here.
  //   List<Integer> result = new ArrayList<>();
  //   preOrderHelper(root, result);
  //   return result;
  // }

  // private void preOrderHelper(TreeNode root, List<Integer> result) {
  //   if (root == null) {
  //     return;
  //   }
  //   result.add(root.key);
  //   preOrderHelper(root.left, result);
  //   preOrderHelper(root.right, result);
  // }

  //iterative way:
  public List<Integer> preOrder(TreeNode root) {
    List<Integer> result = new ArrayList<>();
    if (root == null) {
      return result;
    }
    Deque<TreeNode> stack = new LinkedList<>();
    stack.offerFirst(root);
    while(!stack.isEmpty()) {
      TreeNode cur = stack.pollFirst();
      result.add(cur.key);
      if (cur.right != null) {
        stack.offerFirst(cur.right);
      }
      if (cur.left != null) {
        stack.offerFirst(cur.left);
      }
    }
    return result;
  }
}

assumption: 输入的treenode不为空。

approach ： 用一个stack 来模拟tree的访问顺序。 terminate一个节点的时候， 判断它的右节点是否为空， 不为空offer进stack，再判断它的左节点是否为空，然后再offer进stack。 while 循环， 直到stack为空为止。

O（n），since the travesal，we need visit every single node。