Prevtree
시간 제한2초메모리 제한128 MB
리프 개수가 같은 이진 트리들 중에서 주어진 디스플레이 코드보다 사전순으로 바로 앞에 오는 디스플레이 코드를 구하고, 없으면 0을 출력하는 문제입니다.
문제
엄격 이진 트리는 단말 노드가 아닌 모든 노드가 정확히 두 자식 노드를 가지는 이진 트리이다. 어떤 노드의 단말값은 그 노드를 루트로 하는 부분 트리에 포함된 단말 노드의 개수이다.
아래 트리는 엄격 이진 트리이며, 각 노드에 적힌 수는 그 노드의 단말값이다.
*7
/ \
/ \
/ \
*4 3
/ \ / \
*1 3 *1 2
/ \ / \
*2 1 *1 1
/ \
*1 1
이러한 트리를 전위 순회하면서 루트와 왼쪽 자식인 노드들의 단말값을 차례로 나열한다. 위 그림에서는 * 표시가 있는 노드들이 나열되며, 그 결과는 (7, 4, 1, 2, 1, 1, 1)이다. 이 수열을 그 트리의 표시 코드라고 한다.
엄격 이진 트리의 표시 코드가 주어졌을 때, 같은 개수의 단말 노드를 가지는 트리들 중에서 표시 코드가 사전식 순서로 주어진 표시 코드의 바로 앞에 오는 트리의 표시 코드를 구하시오.
입력
첫째 줄에 표시 코드의 길이 L이 주어진다. 1 <= L <= 10,000이다.
둘째 줄에는 표시 코드를 나타내는 L개의 정수가 공백으로 구분되어 주어진다.
출력
주어진 표시 코드가 사전식 순서로 가장 앞서는 표시 코드라면 0을 출력한다.
그렇지 않다면 사전식 순서로 주어진 표시 코드의 바로 앞에 오는 표시 코드를 출력한다.