题面
编写一个程序,分别读取二叉树上前序树遍历和中序树遍历得到的两个节点序列,并在二叉树上打印后序树遍历得到的节点序列。
输入
第一行给出了一个整数 n,它是二叉树中的节点数。(1≤n≤40)
在第二行中,通过前序树遍历获得的节点 ID 序列以空格字符分隔给出。
在第二行中,通过中序树遍历获得的节点 ID 序列以空格字符分隔给出。
每个节点都有一个从 1 到 n 的唯一 ID。 请注意,根并不总是对应于 1。
输出
将后序树遍历获得的节点 ID 序列打印成一行。 在相邻 ID 之间放置一个空格字符。
输入样例
5
1 2 3 4 5
3 2 4 1 5
输出样例
3 4 2 5 1
#include <iostream>
#include <stack>
#include <vector>
#include <unordered_map>
using namespace std;#define MAX 41// 定义树的节点结构
struct Node {int p, l, r;
};struct Node T[MAX]; // 树节点数组
int n; // 节点的数量
unordered_map<int,int> m;int buildtree(int po[],int ps,int pe,int io[],int is,int ie)
{if(ps>pe||is>ie)return -1;int rootval=po[ps];int rootidx=m[rootval];int leftsize=rootidx-is;T[rootval].p=-1;T[rootval].l=buildtree(po,ps+1,ps+leftsize,io,is,rootidx-1);T[rootval].r=buildtree(po,ps+leftsize+1,pe,io,rootidx+1,ie);if(T[rootval].l!=-1)T[T[rootval].l].p=rootval;if(T[rootval].r!=-1)T[T[rootval].r].p=rootval;return rootval;
}void posorder(int root)
{if(root==-1) return;stack<int> s1,s2;s1.push(root);while(!s1.empty()){int node=s1.top();s1.pop();s2.push(node);if(T[node].l!=-1)s1.push(T[node].l);if(T[node].r!=-1)s1.push(T[node].r);}while(!s2.empty()){cout<<s2.top()<<" ";s2.pop();}
}int main() {int v;int a[41],b[41];scanf("%d", &n);for (int i = 0; i < n; i++) {T[i].p = T[i].l = T[i].r = -1;}for (int i = 0; i < n; i++) {scanf("%d", &v);a[i]=v;}for (int i = 0; i < n; i++) {scanf("%d", &v);b[i]=v;m[v]=i;}int root=buildtree(a,0,n-1,b,0,n-1);posorder(root);return 0;
}