이진트리. [9934]

[1. 문제 설명]

https://www.acmicpc.net/problem/9934

---

[2. 풀이 접근]

먼저 문제에서 주어지는 트리는 완전 이진 트리이다.

완전 이진 트리는 이진 트리의 한 형태로, 

트리의 깊이가 K 일 때, 노드의 개수가 2^K-1 개를 갖는다.

즉, 모든 레벨에 노드가 꽉 차있는 이진 트리이다.

 

트리의 방문 순서를 통해서 트리 구성을 역추적하는 문제는

트리가 재귀적인 특성이라는 것을 이용하도록 한다.

즉, 방문하는 함수를 재귀로 구현하면 된다는 것이다.

 

방문 순서가 문제에 조건으로 주어져 있으므로,

문제 조건을 그대로 함수에 구현하되, 재귀적으로 작성하면 된다.

 

재귀 함수는 보통 아래와 같이 작성하도록 한다.

1. 재귀의 종료 조건
2. 재귀 호출

---

[3. 코드]