题目：https://pintia.cn/problem-sets/994805342720868352/problems/994805380754817024

给出先序和中序，求后序序列

注意点

  1. numLeft = i - inL，一定是减中序的最左
  2. 29行i - 1写成了inL - 1
  3. 建树的代码一定要好好看看，特别是递归式

代码

  1. #include<vector>
  2. #include<algorithm>
  3. #include<iostream>
  4. #include<stack>
  5. #include<string>
  6. using namespace std;
  8. const int maxn = 50;
  9. struct node{
  10.     int data;
  11.     node *lchild;
  12.     node *rchild;
  13. };
  15. stack<int> s;
  16. int pre[maxn], in[maxn], post[maxn];
  17. int num = 0, n;
  18. node* create(int preL, int preR, int inL, int inR){
  19.     if(preL > preR) return NULL;
  20.     node*root = new node;
  21.     root->data = pre[preL];
  22.     //查找下一个根结点
  23.     int i;
  24.     for(i = inL; i <= inR; i++){
  25.         if(in[i] == pre[preL]) break;
  26.     }
  27.     int numLeft = i - inL;
  28.     root->lchild = create(preL + 1, preL + numLeft, inL, inL + numLeft - 1);
  29.     root->rchild = create(preL + numLeft + 1, preR, i + 1, inR);
  30.     return root;
  31. }
  33. void postOrder(node* root){
  34.     if(root == NULL) return;
  35.     postOrder(root->lchild);
  36.     postOrder(root->rchild);
  37.     printf("%d",root->data);
  38.     if(num != n - 1) printf(" ");
  39.     num++;
  40. }
  42. int main(){
  43.     scanf("%d",&n);
  44.     string temps;
  45.     int tempi, preIndex = 0, inIndex = 0;
  46.     for(int i = 0; i < n;){
  47.         cin>>temps;
  48.         if(temps == "Push"){
  49.             scanf("%d", &tempi);
  50.             s.push(tempi);
  51.             pre[preIndex++] = tempi;
  52.         }else if(temps == "Pop"){
  53.             i++;
  54.             tempi = s.top();
  55.             s.pop();
  56.             in[inIndex++] = tempi;
  57.         }
  58.     }
  59.     postOrder(create(0, n - 1, 0, n - 1));
  60.     return 0;
  61. }