二叉树前中后序递归及非递归遍历C++实现完整版

给定一个二叉树，返回它的前中后序遍历。

示例：输入[1,2,3,4,-1,5,6,-1,7,-1,-1,8,-1] ,-1代表无节点(null)，二叉树如下所示：

输出：二叉树的前序、中序、后序遍历序列。

完整实现代码（包括定义数据结构、建树等）如下：

#include<iostream>
#include<string>
#include<vector>
#include<cstring>
#include<stack>
#include<map>
#include<queue>
using namespace std;
struct TreeNode{
    int val;
    TreeNode *left,*right;
    TreeNode(int x):val(x),left(NULL),right(NULL){}
};
//---建树
TreeNode* creaTree(vector<int> x){
    queue<TreeNode*>nodequeue;
    TreeNode *root=new TreeNode(x[0]);
    nodequeue.push(root);
    TreeNode *p=root;
    int i=1;
   while(true){
        p=nodequeue.front();
        nodequeue.pop();
        if(i>=x.size())break;
        if(x[i]!=-1){
            p->left=new TreeNode(x[i]);
            nodequeue.push(p->left);
        }
        i ++;
        if(i>=x.size())break;
        if(x[i]!=-1){
            p->right=new TreeNode(x[i]);
            nodequeue.push(p->right);
        }
        i++;
    }
    return root;
}
class Solution {
public:
    //-------------前序递归---
    vector<int>res1;
    vector<int> recpreorderTraversal(TreeNode* root){
        if(root){
            res1.push_back(root->val);
            recpreorderTraversal(root->left);
            recpreorderTraversal(root->right);
        }
        return res1;
    }
    //------------前序非递归
    vector<int> preorderTraversal(TreeNode* root){
        vector<int>res;
        TreeNode *p=root;
        stack<TreeNode*>s;
        while(p || !s.empty()){
            while(p){
                res.push_back(p->val);
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                s.pop();
                p=p->right;
            }
        }
        return res;
    }
    //---------中序非递归
    vector<int> inorderTraversal(TreeNode* root) {
        stack<TreeNode*>s;
        vector<int>res;
        //map<TreeNode*,bool>instack;
        TreeNode *p=root;
        //s.push(root);
        while(p!=nullptr || !s.empty()){
            while(p!=nullptr){
                s.push(p);
                p=p->left;
            }
            if(!s.empty()){
                p=s.top();
                s.pop();
                //cout<<p->val;
                res.push_back(p->val);
                p=p->right;
            }
        }
        return res;
    }
    //--------------中序递归---------
    vector<int>res2;
    vector<int> recinorderTraversal(TreeNode* root) {
        if (root != nullptr) {
            recinorderTraversal(root->left);
            res2.push_back(root->val);
            recinorderTraversal(root->right);
        }
        return res2;
    }
    //-------------后序递归
    vector<int>res3;
    vector<int> recpostorderTraversal(TreeNode* root) {
        if(root){
            recpostorderTraversal(root->left);
            recpostorderTraversal(root->right);
            res3.push_back(root->val);
        }
        return res3;
    }
    //---------------后序非递归
    vector<int> postorderTraversal(TreeNode* root){
        vector<int>res;
        stack<TreeNode*>s;
        TreeNode *p,*pre= nullptr;
        s.push(root);
        while(!s.empty()){
            p=s.top();
            if((!p->left && !p->right) || ((pre!=nullptr) &&(pre==p->left ||pre==p->right))){
                res.push_back(p->val);
                s.pop();
                pre=p;
            }
            else{
                if(p->right)
                    s.push(p->right);
                if(p->left)
                    s.push(p->left);
            }
        }
        return res;
    }
};

int main(){
    vector<int>x={1,2,3,4,-1,5,6,-1,7,-1,-1,8,-1};
    //cout<<x.size();
    TreeNode *root=creaTree(x);
    vector<int>res=Solution().postorderTraversal(root);
    for(int i=0;i<res.size();i++) {
        cout << res[i] << " ";
    }
    return 0;
}