[BOJ/C++] 5639: 이진 검색 트리

🏅 Gold 5

✏️ 솔루션

✅ 이진 탐색 트리의 전위순회(V-L-R)를 후위순회(L-R-V)로 바꾸기

arr: 50 30 24 5 28 45 98 52 60
현재 노드: 50
서브트리 마지막 인덱스: arr.size()-1

1. 왼쪽 서브트리, 오른쪽 서브트리의 구분점이 되는 인덱스 찾기
   ➡️ 현재 노드 인덱스 다음 노드부터 시작해서 노드 값이 현재 노드 값보다 같거나 클 때까지 노드 인덱스++ 하면서 찾기
2. 현재 상태에서 탐색할 왼쪽 서브트리
   다음 노드: 현재 노드 다음 노드: ex) 30
   서브트리 마지막 인덱스(왼쪽 서브트리의 마지막 노드 인덱스): 서브트리 구분 인덱스 - 1
3. 현재 상태에서 탐색할 오른쪽 서브트리
   다음 노드: 현재 노드 다음 노드: 현재 노드에서 서브트리 구분점 인덱스
   서브트리 마지막 인덱스: 현재 노드의 서브트리 마지막 인덱스 그대로 ➡️ 오른쪽 서브트리이기 때문
4. 2, 3 과정에 해당한다면 현재 노드는 더 이상 서브트리가 없는 리프노드이거나 서브트리를 모두 출력해서 이제 출력할 차례인 노드이기 때문에 현재 노드 값을 출력

✏️ code

#include <iostream>
#include <vector>
using namespace std;

vector<int> arr;

void sol(int nodeIdx, int sub) {  // 현재노드, 서브트리 범위
    int cur=nodeIdx;
    int subIdx=nodeIdx++;   // 왼오 서브트리 구분점이 되는 인덱스 -> 현재 노드 다음 인덱스부터 탐색 시작
    // 현재 노드 다음노드부터 서브트리가 될 수 있기 때문에 서브트리 구분 인덱스를 현재 노드 값보다 작을때까지 갱신
    while (++subIdx<arr.size() && arr[subIdx]<arr[cur]);
    // 이때, subIdx는 서브트리의 왼오를 구분할 수 있는 인덱스
    
    // 왼쪽 서브트리 이어서 트리 탐색
    // 현재 노드 다음 인덱스가 서브트리 구분 인덱스보다 작으면 아직 탐색할 왼쪽 서브트리가 남아있다는 뜻
    // 현재 노드 다음 노드를 루트 노드로 해서 탐색,
    // 이어서 탐색할 왼쪽 서브트리는 서브트리 구분 인덱스-1 -> 여기까지 왼쪽 서브트리 범위이기 때문
    if (nodeIdx<=subIdx-1) sol(nodeIdx, subIdx-1);
    
    // 현재 노드의 우측 서브트리 탐색
    // 서브트리 구분 인덱스보다 서브트리 크기가 크다면 아직 탐색할 오른쪽 서브트리가 남은 것
    if (subIdx<=sub) sol(subIdx, sub);
    
    cout << arr[cur] << '\n';

}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    // 개수 제한없이 입력 받기
    while (cin >> n) arr.push_back(n);
    
    sol(0, arr.size()-1);   // 노드는 제외하고 서브트리 탐색할 것이기 때문에 arr size - 1 이 서브트리 탐색 끝 범위가 됨
    
}