题目粗心：

用栈来模仿一颗二叉树的先序和中序遍历过程,求这课树的后序遍历序列。

算法思路:

首先得说一个论断,就是栈的入栈序列就是一颗二叉树的先序遍历,出栈序列就是一颗二叉树的中序遍历序列,那么这个题目就转化为依据先序和中序求后序遍历序列。那么首先就是依据先序和中序建设二叉树，而后依据这个二叉树进行后序遍历取得后序遍历序列。

递归建设二叉树

假如递归过程中某步的前序区间是$[beginPre,lastPre]$,中序区间是$[beginIn,lastIn]$,那么根节点为$pre[beginPre]$,首先初始化根节点$root$，接着须要在中序遍历中找到根节点的地位$index_root$,而后计算左子树的个数leftTreeLen = index_root-beginIn;这样左子树和右子树在后序和中序遍历中就离开了,紧接着就是左子树递归:

root->left =createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1);

右子树递归:

root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn);

递归的边界就是在区间长度小于0的时候间接返回空即可。

留神点：

  • 1、输出的行数为N的2倍。

提交后果：

AC代码：

#include <stack>#include <string>#include <iostream>#include <vector>using namespace std;struct Node{    int data;    Node* left;    Node* right;};int N;// 节点个数vector<int> pre,In;Node* createTree(int beginPre,int lastPre,int beginIn,int lastIn){    if(beginPre>lastPre) return nullptr;    // 初始化根节点    Node* root = new Node;    root->data = pre[beginPre];    // 在中序序列    int index_root;    for(index_root=beginIn;index_root<=lastIn;++index_root){        if(In[index_root]==root->data) break;    }    int leftTreeLen = index_root-beginIn;    root->left = createTree(beginPre+1,beginPre+leftTreeLen,beginIn,index_root-1);    root->right = createTree(beginPre+leftTreeLen+1,lastPre,index_root+1,lastIn);    return root;}int num = 0;// 输入节点的个数，用来管制输入void postTraverse(Node* root){    if(root== nullptr) return;    postTraverse(root->left);    postTraverse(root->right);    printf("%d",root->data);    if(num<N-1) printf(" ");    ++num;}int main(){    scanf("%d",&N);    string s;    int num;    stack<int> st;    // 输出的数据有2*N行    for (int i = 0; i < 2*N; ++i) {        cin>>s;        if(s=="Push"){            scanf(" %d",&num);            st.push(num);            pre.push_back(num);        } else {            num = st.top();            st.pop();            In.push_back(num);        }    }    Node* root = createTree(0,N-1,0,N-1);    postTraverse(root);    return 0;}