二叉树的前序、中序、后序遍历，可以用递归或迭代两种方法实现。

递归法

//中序遍历
class Solution{
public:
    vector<int> vec;
    vector<int> InOrderRecursive(BT* root, vector<int> vec)
    {    
        if(root==nullptr)
            return vec;
        vec = InOrder(root->left, vec);
        vec.push_back(root->val);
        vec = InOrder(root->right, vec);
        return vec;
    }

迭代法

通过堆栈和智能指针来实现二叉树的迭代遍历
BT.h头文件如下

#ifndef BINARYTREE_H
#define BINARYTREE_H

struct BinaryTree{
    int             val;
    BinaryTree*     left;
    BinaryTree*     right;
    BinaryTree(x):
        val(x), left(nullptr), right(nullptr) {}
}
typedef BinaryTree BT；

#endif

函数主体如下：

中序遍历

class Solution{
public:
    vector<int> InOrderTraversal(BT* root){
        vector<int> vec;
        if(root==nullptr)
            return vec;
        stack<BT*> st;
        shared_ptr<BT> p1 =  make_shared<BT> (BT(val));

        while(p1!=nullptr || !st.empty())
        {
            while(p1!=nullptr)
            {
                st.push(p1);
                p1 = p1->left;
            }
            p1 = st.top();
            st.pop();
            vec.push_back(p1->val);
            p1 = p1->right;
        }
        return vec;
    }

前序遍历

    vector<int> PreOrderTraversal(BT* root){
        vector<int> vec;
        if(root==nullptr)
            return vec;
        stack<BT*> st;
        shared_ptr<BT> p1 =  make_shared<BT> (BT(val));

        while(p1!=nullptr || !st.empty())
        {
            while(p1!=nullptr)
            {
                //前序遍历先将节点值输入进vec中，然后向左把节点压入st中
                vec.push_back(p1->val);
                st.push(p1);
                p1 = p1->left;
            }
            p1 = st.top();
            st.pop();
            p1 = p1->right;
        }
        return vec;
    }

后序遍历

vector<int> PostOrderTraversal(BT* root){
        vector<int> vec;
        if(root==nullptr)
            return vec;
        stack<BT*> st;
        shared_ptr<BT> p1 =  make_shared<BT> (BT(val));
        TreeNode *preVis = root;
        //后续遍历需要考虑到先右节点再根节点
        while(p1!=nullptr || !st.empty())
        {
            //把左子树叶节点放进去
            while(p1!=nullptr)
            {                
                st.push(p1);
                p1 = p1->left;
            }
            p1 = st.top();
            //如果无右子树或右子树已经被访问过，再访问根节点
            if(p1->right==nullptr || p1->right==preVis)
            {
                vec.push_back(p1->val);
                st.pop();
                pre = p1;
                p1 = nullptr;
            }
            else p1 = p1->right;
        }
        return vec;
    }
};

层序遍历

//运用队列来实现
vector<int> levelTraversal(BT* root)
{
    vector<int> vec;
    if(root==nullptr)
        return vec;
    queue<BT*> q;
    q.push(root);
    while(!q.empty())
    {
        TreeNode* temp;
        for(int i=0;i<q.size();++i){
            temp = q.front();
            vec.push_back(temp->val);
            if(temp->left!=nullptr)
                q.push(temp->left);
            if(temp->right!=nullptr)
                q.push(temp->right);
            q.pop();
        }
    }
    return vec;
}