本文共 877 字,大约阅读时间需要 2 分钟。
#include#include #include using namespace std;int n;vector pre, in, post;struct node{ int data; node *l, *r;};node *build(int preL, int preR, int inL, int inR){ if(preL > preR) return NULL; node *root = new node; root->data = pre[preL]; int k; for(k = inL; k <= inR; k++) if(in[k] == pre[preL]) break; int leftnum = k - inL; root->l = build(preL + 1, preL + leftnum, inL, k - 1); root->r = build(preL + leftnum + 1, preR, k + 1, inR); return root;}void postorder(node *root){ if(root == NULL) return; postorder(root->l); postorder(root->r); post.push_back(root->data);}int main(){ cin >> n; pre.resize(n); in.resize(n); for(int i = 0; i < n; i++) cin >> pre[i]; for(int i = 0; i < n; i++) cin >> in[i]; node *root = build(0, n-1, 0, n-1); postorder(root); cout << post[0] << endl; return 0;}
转载地址:http://fptyo.baihongyu.com/