import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    public void preorder(List<Integer> list,TreeNode root){
        if(root==null){
            return ;
        }
        list.add(root.val);
        preorder(list,root.left);
        preorder(list,root.right);
    }
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        // write code here
        List<Integer> list = new ArrayList<>();
        preorder(list,root);
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();++i){
            res[i]=list.get(i);
        }
        return res;
    }
}

方法一：递归

由于对于每个树的左右子树问题都是进行前序遍历，所以可用递归实现。另外需要数组存储遍历结果而且随着递归发生变化，所以将数组作为参数传递，另外一个参数当然是树根节点。参数与题中给出的方法不同，因此需要另设方法实现递归。主方法要求返回int类型的数组，所以要将List中的值复制给一个int型数组。

递归三要素：

1、递归出口：访问到叶子节点后，左右孩子为空，则判空即为出口条件。

2、当前任务：访问当前节点，将值存入数组。

3、向下递归：先从左子树递归，再从右子树递归。

记Java 数组List的用法：

1、声明：List<类型> list = new ArrayList<>();

2、添加元素：list.add(值);

3、访问：list.get(下标);

方法二：用栈，模拟递归

利用栈的先进后出特性，模拟递归，父问题先进入子问题再进入。由于是先序遍历即 根左右 ，所以入栈为先右子树后左子树。开始先让根节点入栈，循环条件是栈不为空，循环内先访问当前栈顶结点，然后右子树若存在则入栈，左子树若存在再入栈。最后所有结点访问完栈为空，跳出循环，给数组赋值后返回即可。

import java.util.*;

/*
 * public class TreeNode {
 *   int val = 0;
 *   TreeNode left = null;
 *   TreeNode right = null;
 *   public TreeNode(int val) {
 *     this.val = val;
 *   }
 * }
 */

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型一维数组
     */
    public int[] preorderTraversal (TreeNode root) {
        //空树返回空数组
        if(root==null){
            return new int[0];
        }
        List<Integer> list = new ArrayList<>();
        Stack<TreeNode> s = new Stack<TreeNode>();
        s.push(root);
	  //遍历
        while(!s.empty()){
            TreeNode node = s.pop();
            list.add(node.val);
            if(node.right!=null){
                s.push(node.right);
            }
            if(node.left!=null){
                s.push(node.left);
            }
        }
        int[] res = new int[list.size()];
        for(int i=0;i<list.size();++i){
            res[i]=list.get(i);
        }
        return res;

    }
}