二叉树的先序遍历

题目：

给定一个二叉树返回其先序遍历的结果

思路：

两种思路,递归和非递归

①递归

void PreOrder(BiTree root)  
{  
    if(root==NULL)  
        return ;  
    printf("%c ", root->data); //输出数据  
    PreOrder(root->lchild); //递归调用，先序遍历左子树  
    PreOrder(root->rchild); //递归调用，先序遍历右子树  
} 

②非递归

思想：二叉树的非递归先序遍历，先序遍历思想：先让根进栈，只要栈不为空，就可以做弹出操作， 每次弹出一个结点，记得把它的左右结点都进栈，记得右子树先进栈，这样可以保证右子树在栈中总处于左子树的下面。

vector<int> preorderTraversal(TreeNode* root) {
        //返回前序遍历
         vector<int> res;
        if(!root)
           return res;
        stack<TreeNode *> st;//定义一个堆栈
        st.push(root);
        while(!st.empty()){
            TreeNode *temp = st.top();
            res.push_back(temp->val);
            st.pop();
            if(temp->right!=NULL){//前序 要先输出根  再左再右  根据栈的先进后出 所以应该先进右
                st.push(temp->right);
            }
            if(temp->left!=NULL){
                st.push(temp->left);
            }
        }
        return res;
    }