#2434 마이 리틀 트리

11  1 s   128 MB  

Description

친구들 안녕하세요! 그동안 잘 있었어요? 오늘은 종이접기가 아닌 특별히 이진 트리에 대해 공부해보도록해요.
이진 트리 (binary tree)는 루트를 가지는 트리 (rooted tree)의 일종으로 각 정점의 자식 (child)이 최대 두개인 트리에요.
여기서 두개의 자식은 정점의 배치 방향에 따라 왼쪽 자식 (left child), 오른쪽 자식 (right child)로 나눌 수 있어요. 이런 이진 트리를 이용해서 순회 (traversal)라는 것을 할 수 있는데, 여기서 순회란 약속에 따라 트리의 모든 정점을 방문하는 방법이에요.
순회하는 방법은 전위 (pre-order)순회, 중위 (in-order)순회, 후위 (post-order)순회 등이 있어요. 이 중에서 전위 순회와 중위 순회는 다음과 같은 의사 코드 (pseudo code)로 표현할 수 있어요.
 
 
너무 쉽죠? 그런데 위의 의사코드에서 정점이 정의되지 않거나 자식이 존재하지 않을 경우 이는 null로 표현되는 것으로 가정해야 해요. 그렇지 않으면 함수가 제대로 돌아가지 않아요.
 
Figure 3: 이진 트리의 예제
 
아저씨랑 위의 이진 트리 그림을 살펴봐요. 뭔가 동그라미가 많네요. 정말 재미있는 모양이죠? 한번 같이 전위 순회와 중위 순회를 해볼까요? 그런데 오늘 친구들한테 알려줄 게 많아서 아저씨는 미리 준비해왔어요.
 
짜자 자잔!
 
• 전위 순회 : 1, 2, 4, 3, 5, 6, 7
• 중위 순회 : 4, 2, 1, 5, 3, 7, 6
 
아직 못했다고 해서 걱정 말아요 친구들이 신입생 때는 어려서 할 수 없었을 텐데 이제는 학부생이 다 되었으니 할 수 있을 거예요!
그런데 친구들, 재미있는 사실이 있어요. 두 개의 순회 결과 (전위, 중위)를 모두 알고 있으면 친구들이 트리의 모양을 알 수 있어요. 참 신기하죠! 그런데 어떻게 하는지 궁금하죠? 그런데 방송 시간이 얼마 남지 않았으니 집에서 숙제로 해보도록 해요. 숙제를 다 했으면 트리를 레벨 (level) 순회해서 출력해봐요.
 
레벨 순회가 뭔지 궁금하다고요? 
레벨 순회는 깊이 (루트에서부터 정점까지 가는 경로의 길이, 거쳐 가는 정점들의 수)순으로 방문하는 방법이 에요. 같은 깊이인 정점들은 트리에서 맨 왼쪽에 있는 것부터 맨 오른쪽에 있는 순으로 방문하게 돼요. 위의 재미있는 모양의 트리를 레벨 순회해볼까요? 역시나 아저씨는 미리 준비해왔어요. 짜잔!
 
• 레벨 순회 : 1, 2, 3, 4, 5, 6, 7
 

Input

입력의 첫 줄에는 이진 트리를 구성하는 정점의 개수 N (1 ≤ N ≤ 100)이 입력됩니다.
둘째 줄에는 N 개의 숫자로 이진 트리에 전위 순회한 결과 (순서대로 방문한 정점의 번호)가 입력되며 숫자 사이는 공백으로 구분됩니다.
셋째 줄에는 N 개의 숫자로 이진 트리에 대한 중위 순회한 결과가 입력되며, 역시 숫자 사이는 공백으로 구분됩니다. 둘째 줄과 셋째 줄에 입력되는 숫자는 1이상 N 이하의 정수이며, 중복되어 입력되는 경우는 없다고 간주합니다.
입력에서 같은 줄에 있는 인접한 숫자들은 공백으로 구분됩니다.

Output

출력은 정점의 번호를 레벨 순회로 방문한 순서대로 출력합니다. 이때 인접한 숫자 사이에는 ‘,’ 문자로 구분되게 출력되어야 합니다.

Sample Input

Sample Output

7
1 2 4 3 5 6 7
4 2 1 5 3 7 6
1,2,3,4,5,6,7

Source

shake! 2015 본선