題目地址
https://www.patest.cn/contests/pat-a-PRactise/1119
題目描述
Suppose that all the keys in a binary tree are distinct positive integers. A unique binary tree can be determined by a given pair of postorder and inorder traversal sequences, or preorder and inorder traversal sequences. However, if only the postorder and preorder traversal sequences are given, the corresponding tree may no longer be unique.
Now given a pair of postorder and preorder traversal sequences, you are supposed to output the corresponding inorder traversal sequence of the tree. If the tree is not unique, simply output any one of them.
Input Specification:
Each input file contains one test case. For each case, the first line gives a positive integer N (<=30), the total number of nodes in the binary tree. The second line gives the preorder sequence and the third line gives the postorder sequence. All the numbers in a line are separated by a space.
Output Specification:
For each test case, first printf in a line “Yes” if the tree is unique, or “No” if not. Then print in the next line the inorder traversal sequence of the corresponding binary tree. If the solution is not unique, any answer would do. It is guaranteed that at least one solution exists. All the numbers in a line must be separated by exactly one space, and there must be no extra space at the end of the line.
Sample Input 1:
71 2 3 4 6 7 52 6 7 4 5 3 1Sample Output 1:
Yes2 1 6 4 7 3 5Sample Input 2:
41 2 3 42 4 3 1Sample Output 2:
No2 1 3 4ac思路
先序+后序 無法判斷二叉樹的唯一性
比如有兩個節點的時候，
先序： 根 左后序： 左 根或者
先序：根 右后序：右 根所以 需要明確是否會出現上述情況
先序第一個節點是根節點，緊接著第二個節點是根節點的左節點還是右節點了？
在后序中查找 先序中的第二個節點
如果后序中的該位置 到 最后（也就是后序中根節點位置） 還有其他數的話，可以判斷，先序中第二個節點肯定左節點（反證法。。。）1 2 3 42 4 3 11 為 根，2 接著，2在后序中，與1隔著兩個數，所以2一定是1的左節點; 3,4成為1的右子樹節點
1 / 2當中間沒有數的時候，就不確定了 例如 3,4 1 / /2 3 / 4還是
1 / /2 3 / 4ac代碼1
#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <iostream>#include <string>#include <vector>#include <queue>#include <algorithm>#include <sstream>#include <list>#include <stack> #include <map> #include <set> #include <iterator> #include <unordered_map>using namespace std;const int INF = 0x7fffffff;typedef long long int LL;const int N = 10000 + 5;int n;vector<int> preOrder;vector<int> postOrder;bool flag;typedef struct node{ int val; struct node* left; struct node* right; node(int _val = -1) { val = _val; left = NULL; right = NULL; }}Bnode;Bnode* Create(int preL, int preR, int postL, int postR){ if(preL > preR) return NULL; Bnode* root = new Bnode(preOrder[preL]); if(preL == preR) return root; // 后序找 pre[preL + 1] int k; for (k = postL; k < postR; k++) { if (postOrder[k] == preOrder[preL + 1]) break; } if(postR - k - 1 > 0) { root->left = Create(preL + 1, preL + 1 + k - postL , postL, k); root->right = Create(preL + 1 + k - postL + 1, preR, k+1, postR -1); }else{ flag = false; root->right = Create(preL + 1, preR, postL, postR - 1); } return root;}vector<int> in;void inOrder(Bnode* root){ if(root != NULL) { inOrder(root->left); in.push_back(root->val); inOrder(root->right); }}int main(){ //freopen("in.txt", "r" , stdin); while(scanf("%d", &n) != EOF) { preOrder.clear(); postOrder.clear(); int tmp; for(int i = 1; i <= n; i++) { scanf("%d", &tmp); preOrder.push_back(tmp); } for(int i = 1; i <= n; i++) { scanf("%d", &tmp); postOrder.push_back(tmp); } flag = true; Bnode* root = Create(0, n-1, 0, n-1); if(flag) { printf("Yes/n"); }else{ printf("No/n"); } in.clear(); inOrder(root); printf("%d", in[0]); for(int i=1;i<n;i++) { printf(" %d",in[i]); } printf("/n"); } return 0;}ac代碼2
#include <cstdio>#include <cstdlib>#include <cmath>#include <cstring>#include <iostream>#include <string>#include <vector>#include <queue>#include <algorithm>#include <sstream>#include <list>#include <stack> #include <map> #include <set> #include <iterator> #include <unordered_map>using namespace std;const int INF = 0x7fffffff;typedef long long int LL;const int N = 10000 + 5;int n;vector<int> preOrder;vector<int> postOrder;bool flag;typedef struct node{ int val; struct node* left; struct node* right; node(int _val = -1) { val = _val; left = NULL; right = NULL; }}Bnode;Bnode* Create(int preL, int preR, int postL, int postR){ if(preL > preR) return NULL; Bnode* root = new Bnode(preOrder[preL]); if(preL == preR) return root; int k; for (k = preL + 1; k <= preR; k++) { if (preOrder[k] == postOrder[postR - 1]) break; } // post[postR -1]是根節點post[postR]的 左或者右 節點 // 如果先序中，post[postR-1] 前面還有其他節點的話，可以判斷其是根節點的左子樹，是確定的 // 否則， post[postT-1] 可以是根節點的左或者右節點 if( k - preL - 1 > 0) { root->left = Create(preL + 1, k-1, postL, postL + k - preL -2); root->right = Create(k, preR, postL + k - preL -1, postR -1); }else{ flag = false; root->right = Create(k, preR, postL + k - preL - 1, postR - 1); } return root;}vector<int> in;void inOrder(Bnode* root){ if(root != NULL) { inOrder(root->left); in.push_back(root->val); inOrder(root->right); }}int main(){ freopen("in.txt", "r" , stdin); while(scanf("%d", &n) != EOF) { preOrder.clear(); postOrder.clear(); int tmp; for(int i = 1; i <= n; i++) { scanf("%d", &tmp); preOrder.push_back(tmp); } for(int i = 1; i <= n; i++) { scanf("%d", &tmp); postOrder.push_back(tmp); } flag = true; Bnode* root = Create(0, n-1, 0, n-1); if(flag) { printf("Yes/n"); }else{ printf("No/n"); } in.clear(); inOrder(root); printf("%d", in[0]); for(int i=1;i<n;i++) { printf(" %d",in[i]); } printf("/n"); } return 0;}
參考思路 小菜在切題 http://www.cnblogs.com/demian/p/6103285.html
