Jogurt

포화 이진 트리는 계층 구조로 배열된 노드들로 이루어진다. 노드 중 하나는 루트 노드이며, 레벨 \(1\)에 있다고 한다. 루트 노드에는 자식 노드가 두 개 있는데, 이들은 레벨 \(2\)에 있다. 그 각각에는 레벨 \(3\)의 자식이 두 개 있고, 이런 식으로 계속된다.

일반적으로 레벨이 \(N\)개인 포화 이진 트리에는 \(2^N - 1\)개의 노드가 있으며, 레벨 \(N\)의 노드를 제외한 각 노드는 자식 노드를 두 개 가진다.

각 노드에는 수를 하나 적을 수 있다. 레벨이 \(N\)개인 포화 이진 트리에 \(1\)부터 \(2^N - 1\)까지의 수를 적되, 레벨 \(i\)의 각 노드에 대해 왼쪽 서브트리의 모든 수의 합과 오른쪽 서브트리의 모든 수의 합의 차의 절댓값이 \(2^{i-1}\)이 되도록 하시오.

예를 들어 루트 노드의 왼쪽 서브트리의 합과 오른쪽 서브트리의 합은 \(1\)만큼 차이 나야 한다. 레벨 \(2\)의 노드의 왼쪽과 오른쪽 서브트리의 합은 \(2\)만큼 차이 나야 한다.

각 수는 정확히 한 번씩 사용해야 한다. 해는 유일하지 않을 수 있다.

입력의 첫째 줄이자 유일한 줄에 트리의 레벨 수인 정수 \(N\) (\(1 \le N \le 15\))이 주어진다.

\(2^N - 1\)개의 정수를 공백으로 구분하여 한 줄에 출력한다. 트리의 전위 순회이다. 전위 순회는 먼저 루트 노드의 수를 출력하고, 그 다음 왼쪽 서브트리를 (역시 전위 순회로) 출력하고, 그 다음 오른쪽 서브트리를 출력한다.

riseoj 작성

출처 COCI 2006/2007 Contest 4