根据一颗二叉树的先序遍历结果和中序遍历结果确定后序遍历结果。
先递归建树，后DFS。代码写了详细的注释~~~~
至今还不会用指针写数据结构。。只会用结构体模拟。。。
#include#include #include using namespace std;const int maxn = 1111;struct abc{ int left, right, date;}node[maxn];int xian[maxn], zhong[maxn];int fxian[maxn], fzhong[maxn];int flag[maxn];int ans[maxn];int sum, uu;void gettree(int ll, int rr, int fn)//ll和rr表示的是中序的区间{ int i, maxn = -99999999, minn = 99999999; //minn maxn为中序ll到rr这段区间在先序的区间 for (i = ll; i <= rr; i++) { if (fxian[zhong[i]] > maxn) maxn = fxian[zhong[i]]; if (fxian[zhong[i]] < minn) minn = fxian[zhong[i]]; } //中序ll到rr这段区间的节点为对应的先序序列中的第一个 node[fn].date = xian[minn]; //这段区间的节点在中序的位置 int yy = fzhong[xian[minn]]; //构造左子树 if (yy - ll != 0) { sum++; node[fn].left = sum; gettree(ll, yy - 1, sum); } //构造右子树 if (rr - yy != 0) { sum++; node[fn].right = sum; gettree(yy + 1, rr, sum); }}void dfs(int wei)//后序遍历 先遍历左儿子 再遍历右儿子 最后遍历节点{ //遍历左儿子 if (node[wei].left == -1) flag[node[wei].left] = 1; else { dfs(node[wei].left); if (flag[node[wei].left] == 0) ans[uu] = node[node[wei].left].date, uu++; flag[node[wei].left] = 1; } //遍历右儿子 if (node[wei].right == -1) flag[node[wei].right] = 1; else { dfs(node[wei].right); if (flag[node[wei].right] == 0) ans[uu] = node[node[wei].right].date, uu++; flag[node[wei].right] = 1; } //遍历节点 flag[wei] = 1; ans[uu] = node[wei].date, uu++; }int main(){ int n, i; while (~scanf("%d", &n)) { sum = 1; uu = 0; memset(flag, 0, sizeof(flag)); for (i = 0; i <= maxn - 10; i++) node[i].date = -1, node[i].left = -1, node[i].right = -1; for (i = 1; i <= n; i++) scanf("%d", &xian[i]); for (i = 1; i <= n; i++) scanf("%d", &zhong[i]); for (i = 1; i <= n; i++){fxian[xian[i]] = i; fzhong[zhong[i]] = i;} gettree(1, n, 1); dfs(1); for (i = 0; i < uu; i++) { if (i