완전 이진 트리
시간 제한1초메모리 제한128 MB
레벨 N인 완전 이진트리에 1부터 2^N-1까지 수를 채워 각 내부 노드에서 좌우 부분트리 합의 차가 2^D가 되도록 하고 전위순회로 출력하는 문제입니다.
문제
완전 이진 트리는 계층적인 구조를 가진다. 루트 노드의 레벨은 0이고, 루트의 두 자식은 레벨 1이다. 일반적으로 어떤 노드의 레벨이 D라면 그 자식의 레벨은 D + 1이다.
레벨이 N인 완전 이진 트리는 모든 잎이 레벨 N - 1에 있으며, 전체 노드 수는 2^N - 1개이다. 레벨이 N - 1이 아닌 모든 노드는 왼쪽 자식과 오른쪽 자식을 하나씩 가진다.
1부터 2^N - 1까지의 정수를 각 노드에 하나씩 적어야 한다. 모든 정수는 정확히 한 번씩 사용해야 한다. 또한 레벨이 D인 모든 내부 노드에 대해, 왼쪽 서브트리에 적힌 수의 합과 오른쪽 서브트리에 적힌 수의 합의 차이의 절댓값은 2^D이어야 한다.
예를 들어 루트에서는 두 서브트리 합의 차이가 1이어야 하고, 레벨 1의 내부 노드에서는 차이가 2이어야 한다.
N이 주어졌을 때 조건을 만족하도록 완전 이진 트리의 각 노드에 수를 적고, 그 결과를 출력하시오.
입력
첫째 줄에 트리의 레벨 N이 주어진다. (1 <= N <= 15)
출력
조건을 만족하도록 수를 적은 완전 이진 트리를 전위 순회한 결과를 첫째 줄에 출력한다. 답이 여러 가지라면 그중 아무 것이나 출력해도 된다.