프로그램 명: coci_obilazak
제한시간: 1 초
아래 그림과 같이 높이가 K인 완전 이진 트리가 있다.
이중 오른쪽 트리를 각 레벨마다 왼쪽 노드에서부터 오른쪽 노드까지 차례대로 읽으면 3 / 6, 2 / 1, 4, 5, 7이 된다.
한편, 이 트리를 중위 순회하면 1, 6, 4, 3, 5, 2, 7이 된다.
트리를 중위 순회한 결과가 주어질 때, 이 트리를 각 레벨마다 왼쪽 노드에서부터 오른쪽 노드까지 차례대로 읽는 프로그램을 작성하여라.
입력 형식
-
첫 번째 줄에는 트리의 높이 K (1 ≤ K ≤10)이 주어진다.
-
두 번째 줄에는 2^K-1개의 수가 주어지는데, 트리를 중위 순회한 결과값이 공백을 사이에 두고 주어진다.
출력 형식
각 줄에, 각 레벨의 노드들을 왼쪽에서 오른쪽까지 읽은 결과를 공백을 사이에 두고 출력한다.
Little Mirko has paid a touristic visit to a village nearby Donji Andrijevci, a town in Slavonia. As it
happens, the arrangement of streets in the village looks awfully familiar to the shape of a perfect binary
tree of the order K. A perfect binary tree of order K consists of 2K - 1 nodes arranged in K levels (just
like in the image). Each node contains a building labeled with a house number. Moreover, all buildings
but the ones in the last level have a left and right child (see the image again).
Mirko has visited all the buildings in a village and noted down the exact entrance order. Now he wants
to describe to you how the village looks like, but he can't quite remember. Luckily, he remembers the
way in which he visited the buildings:
-
in the beginning, he was standing in front of the only building in the first level
-
if the building which he is currently standing in front of has a left child which he hasn't visited
yet, he will move in front of the left child
-
if the building doesn't have a left child or he has already visited it, he will enter the current
building and write its house number on his paper
-
if he has already visited the current building and the building has a right child, he will move in
front of the right child
-
if he has visited the current building and its left and right child, he will return to the parent of
the current building
After visiting the villages in the pictures above, the paper would look like this: 2-1-3 for the first village
and 1-6-4-3-5-2-7 for the second village. Write a programme to help Mirko reconstruct the order of
house numbers on each level.
입력
The first line of input contains the integer K (1 ≤ K ≤ 10), the number of levels of the village Mirko
just visited.
The second line of input contains 2K integers, the sequence of house numbers on Mirko's paper. The house numbers will be unique and from the interval [1, 2K
].
출력
The output must consist of K lines. The i th line must contain the sequence of house numbers in the i
th level of the village.
입출력 예
input
2
2 1 3
output
1
2 3
input
3
1 6 4 3 5 2 7
output
3
6 2
1 4 5 7
Clarification of the first and second example: The examples correspond to the images in the task.
번역:functionx
출처:/coci/2013-2014/contest5 2번
[질/답]
[제출 현황]
[푼 후(1)]