Kate is learning about binary tree. She think she know everything you know about binary trees. Wait, you don't know binary tree? Find a book about data structures, and it will just take you about three minutes. Now here is a binary tree:
3
/ \
/ \
2 4
/ \ \
/ \ \
0 1 6
/
/
5
Kate think she also know something that you may not notice. First, for some type of binary trees, only the leaf nodes have the meaning (leaf node is the node which has no sub trees, for the tree above, the leaf nodes are 0 1 5), an example is the Huffman Tree. Second, she guess that if you know the preorder traversal and the postorder traversal of a binary tree, you can ensure the leaf node of the tree, and their order.
For the tree above, the preorder travesal is 3 2 0 1 4 6 5 and the postorder travesal is 0 1 2 5 6 4 3, the leaf nodes in order(from left to right) are 0 1 5.
But now the problem is she just guess it, if you can find a way to print a tree's leaf nodes in order using its preorder traversal and postorder traversal, you can say "she is right!"
Input Specification
The input file will contain one or more test cases. In each test case there is a integer n (0<=n <= 10000), indicating the tree have n nodes, then followed two lists of integers, either contains n integers in the range of 0 and n-1 (both included), the first list is the preorder traversal, and the other is the postorder traversal.
Input is terminated by an interger -1;
Output Specification
For each test case, print the tree's leaf nodes in order, each in a line.
Sample Input
7
3 2 0 1 4 6 5
0 1 2 5 6 4 3
-1
Sample Output
0
1
5
根據(jù)一個(gè)重要結(jié)論，無(wú)論是先根還是后根遍歷，左子樹(shù)的結(jié)點(diǎn)總是出現(xiàn)在右子樹(shù)結(jié)點(diǎn)的前面
G
/ \
F B
/ / \
K C H
/ \ /
D E J
\
A
/
I
不論先根后根，左子樹(shù)的結(jié)點(diǎn)總是出現(xiàn)在右子樹(shù)結(jié)點(diǎn)的前面。
G為根樹(shù)，先根次序時(shí)G后跟F，后根次序時(shí)F前有DIAEKF，故DIAEKF為G的左子樹(shù)的結(jié)點(diǎn)，
CJHB為G的右子樹(shù)的結(jié)點(diǎn)。且左右子樹(shù)的先根序?yàn)椋篎KDIAE，BCHJ。
遞歸處理兩子樹(shù)即可搞定
void find(int preb,int pree,int postb,int poste)
{
int i=s(pre,post[poste-1]);
int j=s(post,pre[preb+1]);
//添加處理的代碼
//判斷是否有左/右支
find(preb+1,i-1,postb,j);
find(i,pree,j+1,poste-1);
}
但是上面的思路是錯(cuò)誤的?。。。。。。。。。。。。?！只知道先序和后序不能能推出樹(shù)來(lái)
只有中序和先序或者中序和后序才可以
不然只知道根節(jié)點(diǎn),但是哪些是左子樹(shù)哪些是右子樹(shù)就不知道了
比如先序時(shí)1234
后序是4321的二叉樹(shù)有8種比如：
1 1
\ /
2 2
/ /
3 3
\ /
4 4
正確思路：先遍歷后根次序，第一個(gè)一定為葉子，設(shè)為當(dāng)前結(jié)點(diǎn)，然后依次檢測(cè)，如果該點(diǎn)在先根序列中位于當(dāng)前節(jié)點(diǎn)的后面，則為葉子節(jié)點(diǎn)，同時(shí)更新當(dāng)前結(jié)點(diǎn)。