友情提示：這題非常值得自己思考獨立做出來，請反復確認后再往下拉

1119. Pre- and Post-order Traversals (30)

時間限制 400 ms
內存限制 65536 kB
代碼長度限制 16000 B
判題程序 Special 作者 CHEN, Yue

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: 7 1 2 3 4 6 7 5 2 6 7 4 5 3 1 Sample Output 1: Yes 2 1 6 4 7 3 5 Sample Input 2: 4 1 2 3 4 2 4 3 1 Sample Output 2: No 2 1 3 4 題意：給出樹的前序后序遍歷，輸出中序。不能確定時，任選一種輸出

分析：和前中、后中一樣，我們需要找到前后遍歷的特殊點

? ? ? ? ? ?我最先感覺，pre的最后一個（5）和post的第一個（2），分別代表mid中最右和最左

? ? ? ? ? ?然后發現 如果pre的第一個（1） 和post的最后一個（1）相等，那么1是根節點

? ? ? ? ? ?_(:з」∠)_接著就迫不及待開始做了，一頓騷操作以后我發現還做不了

? ? ? ? ? 再看的時候發現：雖然單看pre沒辦法 確定（2）是（1）的左子樹還是右子樹，但是（1）在post中的前一個是（3），那么（3）要么是（1）的左子樹要么是（1）的右子樹，而pre當中（2）再過去才是（3），所以說明，（2）是（1）的左子樹，（3）是（1）的右子樹。那么剩下的（4）（5）（6）（7）呢？ 再確認，（2）和（3）分開以后，（4）（5）（6）（7）明顯就只能是（3）的子樹

? ? ? ? ? 有了這一點，就可以開始做了

? ? ? ? ? 用遞歸分治，對（3）的左右子樹再分別判斷，逐步縮小，直至確認。以下圖做詳細說明

?1.首先我們發現post(1)? 前一位是 3，對應到pre(3)當中pre(3)與pre(1)中有間隔。說明：（2）是（1）的左子樹，（3）是（1）的右子樹

? ? ? ? ?2.開始遞歸，在橙色圈中我們可以發現，（5）是（3）的右子樹，（4）是3的左子樹

? ? ? ? ?3.post(4)前一位（7）對應到pre當中與pre(4)中間仍然數字間隔，所以（6）是（4）的左子樹，（7）是（4）的右子樹

? ? ? ? ?4.（1）的左子樹（2），可以看出左邊是（1）不能用，右邊則都在（3）的范圍內，所以（2）兩個子樹為空

? ? ? ? ?5.（3）的右子樹（5），同上，兩個子樹為空

? ? ? ? ??

? ? ? ? ?那么，我們要怎么判斷有沒有唯一解呢？如果每一個非葉節點都像上面（1）（3）（4）一樣，顯然是有唯一解的，但是如果題中第二個例子的（3），它的子樹（4）是與（3）緊連的，中間沒有數字隔開，這是就無法判斷是左子樹還是右子樹。所以只要當我們發現有某個非葉節點只有一個孩子的時候，就可以輸出No了

代碼：

#include<iostream> using namespace std; int pre[40]={0}; int post[40]={0}; int n,judge=1; struct node {int data;struct node *lchild,*rchild; }; int find(int a[],int data){for(int i=0; i<n; i++)if(a[i] == data) return i; } struct node *creat(struct node *root, int preStart, int preEnd, int postStart, int postEnd){if(pre[preStart] == post[postEnd]){root = new struct node();root->data = pre[preStart];} if(preStart == preEnd || postStart == postEnd) return root; int i = find(pre, post[postEnd - 1]);//i是root右孩子在pre的索引 int j = find(post, pre[preStart + 1]);//j是root左孩子在post的索引 if(i - preStart >= 2) { root->lchild = creat(root->lchild, preStart+1, i-1, postStart, j);root->rchild = creat(root->rchild, i, preEnd, j+1, postEnd-1);}else{//其實只剩一種可能，即 i == preStart+1 judge=0;root->rchild = creat(root->rchild, i, preEnd, j+1,postEnd-1);}return root; } void midOut(struct node* root){static int cnt=0;if(root->lchild) midOut(root->lchild);if(root) cnt == 0 ? cout<< root->data : cout<<" "<<root->data;cnt++;if(root->rchild) midOut(root->rchild); } int main() {cin>>n; for(int i=0; i<n; i++)cin>>pre[i];for(int i=0; i<n; i++)cin>>post[i];struct node *root;root = creat(root, 0, n-1, 0, n-1);judge==1? cout<<"Yes"<<endl:cout<<"No"<<endl;midOut(root);cout<<endl; }
結尾：這題感覺有些可惜，因為前面想了很久，中間試過很多“奇思妙想”的方法，當我想到先確認根再確認左右子樹時，預估代碼要寫八九十行而且很繁瑣，就忍不住看了別人的題解。 結果發現就是這個思路 _(:з」∠)_。? 不過那時候沒想到遞歸，還在撲哧撲哧上下左右想著點，所以弄的很復雜。? 不過人家直接數組就記錄了mid，然后直接輸出，感覺還是很炫酷。

? ? ? ? ??

轉載于:https://www.cnblogs.com/childwang/p/8280262.html

總結

以上是生活随笔為你收集整理的1119. Pre- and Post-order Traversals (30)的全部內容，希望文章能夠幫你解決所遇到的問題。

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