JOJ2035: Leaf Nodes

2035: Leaf Nodes
Status
In/Out
TIME Limit
MEMORY Limit
Submit Times
Solved Users
JUDGE TYPE
stdin/stdout
1s
10240K
224
104
Standard
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

사고방식은 이렇다. 왜냐하면 선근은 중좌우, 후근은 좌우중간이기 때문에 왼쪽은 모두 오른쪽 앞에 있다.후근이 두루 다니는 서열에서 앞으로 가면 예를 들어 후근이 두루 다니는 첫 번째는 틀림없이 잎이기 때문에 선근이 두루 다니는 서열에서 그 결점을 찾으면 그 앞에 있는 것이 중, 모두 -1로 표시되기 때문에 잎이 아닐 것이다.
알고리즘에는 주로 COUNT로 번호를 기록하고 -1로 표시하며 이해합니다!
 
이 알고리즘의 정확성은 오른쪽 나무의 첫 번째는 틀림없이 잎 노드이다. 선차적 역주행과 후차적 역주행에서 왼쪽은 모두 오른쪽 앞에 있기 때문이다. 그러면 우리가 B수조(후차적 역주행)에서 잎 노드를 찾으면 A수조(선차적 역주행)에서 잎의 조상들을 모두 표시해서 그들이 잎이 아니라고 표시한다.항상 왼쪽을 먼저 훑어보기 때문에, 우리가 이렇게 표시해도 오른쪽의 잎사귀에 영향을 주지 않을 것이다.
 
#includeint a[10000],b[10000];int main(){freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);int n,i,j,k,count;while((scanf("%d",&n),n)>0){   for(i=0;i