题意理解

输入一个二叉树，通过先序遍历将节点值依次放入数组并输出。

方法一

递归
由于是先序遍历，我们先输出当前节点的值，再遍历其左孩子，最后遍历其右孩子。对于每个孩子也是同样的操作。递归边界是当前节点为空。

先序遍历的顺序示意图如下：

具体代码如下：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> ans;
    
    void first(TreeNode* root) {
        if (root==NULL) return;
        ans.push_back(root->val);
        first(root->left);
        first(root->right);
        return;
    }
    
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        first(root);
        return ans;
    }
};

时间复杂度： $O(N)O(N)$。每一个节点都遍历了一遍，N为节点个数。
空间复杂度： $O(N)O(N)$。递归栈的深度在最坏情况下为N；除此之外还使用了一个数组ans记录先序遍历的结果，其长度也为N。

方法二

栈
递归过程使用到了栈，我们也可以尝试自己用栈模拟递归。

从根节点开始，压入栈。当栈不为空时，弹出栈顶元素，先将其右子树压入栈，再将其左子树压入栈。不断重复以上操作。因为栈底元素到最后才被弹出，所以先把右子树入栈才能实现先序遍历。

具体代码如下：

/**
 * struct TreeNode {
 *	int val;
 *	struct TreeNode *left;
 *	struct TreeNode *right;
 *	TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 * };
 */
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param root TreeNode类 
     * @return int整型vector
     */
    vector<int> ans;
    
    
    vector<int> preorderTraversal(TreeNode* root) {
        // write code here
        if (root == NULL) return ans;
        stack<TreeNode*> a;
        a.push(root);
        while (!a.empty())
        {
            TreeNode *p = a.top();
            ans.push_back(p->val);
            a.pop();
            //先把右子树入栈再把左子树入栈
            if (p->right!=NULL)
            {
                a.push(p->right);
            }
            if (p->left!=NULL)
            {
                a.push(p->left);
            }
        }
        return ans;
    }
};

时间复杂度： $O(N)O(N)$。每一个节点都遍历了一遍，N为节点个数。
空间复杂度： $O(N)O(N)$。栈的深度在最坏情况下同样为N；除此之外还使用了一个数组ans记录先序遍历的结果，其长度也为N。