[백준 5639번] 이진 검색 트리 (C++)

문제링크 : https://www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int tree[10001];

void postorder(int s, int e) //후위순회 (left, right, root)
{
    if(s>=e) return;
    if(s == e-1) //하나씩 출력 (left, right)
    {
        cout << tree[s] <<'\n';
        return;
    }
    int idx = s+1;
    while(idx<e)
    {
        if(tree[s]<tree[idx]) break; //더 큰요소 나오면 멈춤
        idx++; //더 큰 요소 위치 저장
    }

    postorder(s+1, idx); //left
    postorder(idx, e); //right
    cout << tree[s] << '\n'; //root
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    int cnt = 0;
    while(cin >> N)
    {
        tree[cnt++] = N;
    }
    postorder(0, cnt);

    return 0;
}

후위순회를 통해 출력하는 이진 트리 문제이다.

후위순회의 순서는 left, right, root이다.

 

문제에서 해당 이진 트리는 

노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작고

노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다고 하였다.

이를 통해서 문제를 해결할 수 있다.

 

일단 처음에 트리에 수를 담고 후위순회를 진행할때, 일단 처음에 들어온 값은 루트이기에 그대로 출력해주면 되지만, 후위순회에서 root 출력은 마지막이기에 항상 left 탐색과 right 탐색에 대해 재귀를 돌리고 나서 마지막에 출력한다.

 

그리고 현재 값보다 큰 값이 나오는 인덱스를 찾는다. 

해당 인덱스를 찾았으면 [현재 시작점 + 1 ~ 해당 인덱스]를 left로 [해당 인덱스 ~ 마지막 점]를 right로 다시 재귀를 돌려서 탐색을 돌린다.

위에서 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작기 때문에 [현재 시작점 +1 ~ 인덱스]를 left로 재귀 탐색하는 것이다.

반대로 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크기에, 위 반복문에서 큰 값이 나오는 인덱스를 찾고 종료하기에 [해당 인덱스 ~ 마지막 점]까지를 right로 두면 되는 것이다.

 

이를 반복하여 s == e-1 이 되는 시점에 tree[s]를 출력해주면 된다.

left 탐색을 통해 왔을 때는 2개가 남고, right 탐색을 통해 왔을 때는 비교할것없이 1개지만 현재 위치가 s이므로 tree[s]를 출력해야 한다.