解题过程的小记录，如有错误欢迎指出。
难度：四星（给出先序和中序求后序，数据的读取是难点）
小导航~
- 题目分析
- 注意点
- 我的解题过程
- 思路
- bug
- 代码
- dalao的代码
- 借鉴点
题目分析
给出先序数列和中序数列，要求输出后序数列（push进去的顺序是先序，利用栈pop出来的顺序是中序）
注意点
要通过先序、后序、中序中其中几个get到二叉树的结构，必须要有中序
我的解题过程
思路
本题的基本思路和上一题一致，难点在于如何通过给出的Push和Pop语句读取到数据
- 先读入一个string（string以空格判断结尾）
- 然后判断这个string是Push还是Pop，如果是Push的话紧跟着再读入一个数据data，插入进先序数列并入栈，如果是Pop，就出栈并且插入中序数列
- 读取了先序和中序数列后的操作就非常常规了
bug
刚开始用getline获取一行Pop或者Push，然后直接读取读到的string[index]来转换为num，这样只能用作一位数，如果是多位数的话emm也可以用substr进行解决吧，但还是采用再读入一个int比较方便一些
代码
#include<iostream>
#include<stack>
#include<string>using namespace std;int pre[35], in[35], n, cnt = 0;struct node {int data;node *lchild, *rchild;
};node* create(int preL, int preR, int inL, int inR) {if (preL > preR) return NULL;node *root = new node;root->data = pre[preL];int i = inL;for (i; i <= inR; i++) {if (in[i] == pre[preL]) break;}int numLeft = i - inL;root->lchild = create(preL + 1, preL + numLeft, inL, i - 1);root->rchild = create(preL + numLeft + 1, preR, i + 1, inR);return root;
}void postorder(node *root) {if (root == NULL) return;postorder(root->lchild);postorder(root->rchild);printf("%d", root->data);cnt++;if (cnt != n) printf(" ");
}int main()
{scanf("%d\n", &n);stack<int> temp;int preindex = 0, inindex = 0;for (int i = 0; i < 2 * n; i++) {string s;cin >> s;if (s[1] == 'u') {//Pushint num;cin >> num;temp.push(num);pre[preindex++] = num;}else {//Popint num = temp.top();temp.pop();in[inindex++] = num;}}node *root = create(0, n - 1, 0, n - 1);postorder(root);return 0;
}
dalao的代码
全部代码因版权原因不放出来，大家可以自行去柳神博客购买或者参考晴神的上机笔记~
借鉴点
本题代码参考自己和晴神的即可（基本一致）