题意：
        给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

方法一：
递归

思路：
        核心：先序递归要按照“根节点->左儿子->右儿子”的顺序遍历树。
        
 

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        pre(root);//先序遍历
        return res;
    }
    
    void pre(TreeNode *root){//递归先序遍历
        if(root==nullptr)
            return;
        res.push_back(root->val);
        pre(root->left);
        pre(root->right);
    }
};

时间复杂度：
空间复杂度：

方法二：
栈实现非递归

思路：
        栈实现先序遍历。
        初始化一个存储树节点的栈空间，遍历指针 p=root。
        外层循环的条件是遍历指针 p 非空或栈非空，
        内层循环则是
                从根节点开始，循环的遍历左儿子入栈；
                当左儿子为空时，则弹栈并指向弹出元素的右儿子。
        
        其中，入栈序列则是树的先序遍历序列。

class Solution {
public:
    vector<int> res;
    vector<int> preorderTraversal(TreeNode* root) {
        stack<TreeNode*> st;//栈
        TreeNode* p=root;
        while(p||!st.empty()){//循环
            while(p){//遍历左儿子入栈
                st.push(p);
                res.push_back(p->val);
                p=p->left;
            }
            p=st.top();//弹栈
            st.pop();
            p=p->right;//遍历右儿子
        }
        return res;
    }
    
    
};

时间复杂度：
空间复杂度：