[BOJ] 18240번 : 이진 탐색 트리 복원하기

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

18240번: 이진 탐색 트리 복원하기

---

풀이

이진 탐색 트리의 모양이 정해지면, (중위순회의 방문 순서) = (그 노드의 값)으로 해당 노드의 값을 찾을 수 있다.

 

다만, 이진 탐색 트리를 만들 수 없는 경우가 생기는데, 바로 앞에 깊이 i인 경우가 없는데 깊이 i+1인 경우가 나오는 경우이다. 이 경우를 자세히 살펴보면 아래와 같다.

• dep[i - 1] < dep[i] / 2 + 1 인 경우에는 깊이 i의 노드를 추가할 수 없다. (dep[i] = 현재까지 깊이 i인 노드의 개수)

 

구현을 해보자!

일단 입력을 받으면서 '이진 탐색 트리를 만들 수 있는지 검사하기'와 'dep[i] 배열 채우기'를 한다.

다음으로는 인오더로 트리를 탐색하면서 dv[i] (0 <= i <= n)를 채우면 된다.

(dv[i] = 깊이가 i인 노드들의 중위순회 방문 순서들)

출력 시에는, 항상 이진 탐색 트리의 왼쪽 자식부터 채워나간다라고 생각하고, dv[i]의 첫 번째 원소부터 쓰면 된다.

이 부분이 위에서 언급한, 이진 탐색 트리의 모양을 정하는 부분이다.

---

코드

ll n;
ll a[300005];
ll dep[300005];
ll ans[300005];
ll val;
deque<ll> dv[300005];

void inorder(ll now)
{
    if (dep[now + 1] > 0)
    {
        inorder(now + 1);
        dep[now + 1]--;
    }
    dv[now].push_back(++val);
    if (dep[now + 1] > 0)
    {
        inorder(now + 1);
        dep[now + 1]--;
    }
}

void solve()
{
    dep[0] = 1;
    cin >> n;
    for (int i = 1; i <= n - 1; i++)
    {
        cin >> a[i];
        if (dep[a[i] - 1] >= dep[a[i]] / 2 + 1) dep[a[i]]++;
        else
        {
            cout << -1;
            return;
        }
    }
    inorder(0);
    cout << dv[0][0] << ' ';
    for (int i = 1; i <= n - 1; i++)
    {
        cout << dv[a[i]][0] << ' ';
        dv[a[i]].pop_front();
    }
}