題干：

Input

The input will contain one or more test cases.?
Each test case consists of one line containing two strings preord and inord, representing the preorder traversal and inorder traversal of a binary tree. Both strings consist of unique capital letters. (Thus they are not longer than 26 characters.)?
Input is terminated by end of file.?
?

Output

For each test case, recover Valentine's binary tree and print one line containing the tree's postorder traversal (left subtree, right subtree, root).

Sample Input

DBACEGF ABCDEFG BCAD CBAD

Sample Output

ACBFGED CDAB

題目大意：

給定一棵樹的先序中序，讓你輸出后序遍歷的序列。

解題報告：

直接模擬

AC代碼：

#include<cstdio> #include<iostream> #include<algorithm> #include<queue> #include<map> #include<vector> #include<set> #include<string> #include<cmath> #include<cstring> #define F first #define S second #define ll long long #define pb push_back #define pm make_pair using namespace std; typedef pair<int,int> PII; const int MAX = 2e5 + 5; struct Node {char val;int l,r; } p[MAX]; int tot; char q[MAX],z[MAX],h[MAX]; int dfs(char q[],char z[],int len) {if(len == 0) return -1;int cur = ++tot;p[cur].val = q[1];p[cur].l = p[cur].r = -1;if(len == 1) return cur;int tar = 0;for(int i = 1; i<=len; i++) {if(z[i] == q[1]) {tar = i;break;}} p[cur].l = dfs(q+1,z,tar-1);p[cur].r = dfs(q+tar,z+tar,len-tar);return cur; } void out(int cur) {if(p[cur].l != -1) out(p[cur].l);if(p[cur].r != -1) out(p[cur].r);printf("%c",p[cur].val); } int main() {while(~scanf("%s%s",q+1,z+1)) {tot=0;int len = strlen(q+1);dfs(q,z,len);out(1);puts("");} return 0 ; }

?

總結

以上是生活随笔為你收集整理的【POJ - 2255】Tree Recovery （给定树的先序中序，输出后序）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。