Binary Tree Preorder Traversal

• 描述
  Given a binary tree, return the preorder traversal of its nodes’ values. For example: Given binary tree
  {1, #, 2, 3}, return [1, 2, 3].

Note: Recursive solution is trivial, could you do it iteratively?

• 使用非递归进行先序遍历，要借助栈（后进先出），先把左子树依次进栈，存入到结果集，这时候结果集保留了左子树的节点值，接着弹栈，如果弹出的节点有右子树，则把右子树进栈，并保存到结果集

• 时间复杂度O(n)，空间复杂度O(n)

• 中序遍历只需要把输出结果的位置调换一下即可

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

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

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

// 解法2， 深度优先搜索DFS的思想
public class Solution1 {
    public static List<Integer> preorderTraverse(TreeNode root) {
        List<Integer> result = new ArrayList<>();
        if(root == null)
            return result;
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode p = stack.pop();
            result.add(p.val);
            if(p.right != null) stack.push(p.right);
            if(p.left != null)  stack.push(p.left);
        }
        return result;
    }
}