백준 5639번 [이진 검색 트리](C++)-yes6686- 티스토리

백준 문제 풀이: 5639 [이진 검색 트리]

---

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

문제 설명:

이진 검색 트리의 전위 순회(preorder traversal)가 주어질 때, 해당 트리의 후위 순회(postorder traversal) 결과를 출력하는 문제입니다.

입력:

• 입력은 여러 줄로 이루어져 있으며, 각 줄에는 노드의 값이 주어집니다. (1 ≤ 노드 값 ≤ 100,000)
• 노드의 개수는 10,000개를 넘지 않습니다.

출력:

• 후위 순회 결과를 한 줄에 하나씩 출력합니다.

---

문제 해결 코드

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

// 후위 순회 결과를 출력하는 재귀 함수
void postorder(vector<int>& arr, int start, int end) {
    if (start >= end) return; // 노드가 없으면 종료
    int root = arr[start];
    int split = start + 1;

    // 오른쪽 서브트리의 시작점을 찾음
    while (split < end && arr[split] < root) {
        split++;
    }

    // 왼쪽 서브트리 탐색
    postorder(arr, start + 1, split);

    // 오른쪽 서브트리 탐색
    postorder(arr, split, end);

    // 현재 루트 출력
    cout << root << '\n';
}

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

    vector<int> arr;
    int x;

    // 입력받기
    while (cin >> x) {
        arr.push_back(x);
    }

    // 후위 순회 출력
    postorder(arr, 0, arr.size());

    return 0;
}

예제

입력:
50
30
24
5
28
45
98
52
60

출력:
5
28
24
45
30
60
52
98
50

---

코드 설명

• 전위 순회에서 후위 순회 변환:
  • 전위 순회의 첫 번째 값은 항상 루트입니다.
  • 루트보다 작은 값들은 왼쪽 서브트리를 구성하고, 루트보다 큰 값들은 오른쪽 서브트리를 구성합니다.
• 재귀적 탐색:
  • 루트와 왼쪽, 오른쪽 서브트리를 각각 탐색합니다.
  • 탐색 순서는 왼쪽 → 오른쪽 → 루트로 후위 순회의 규칙을 따릅니다.

시간 복잡도

• 입력 크기가 n일 때, 각 노드를 한 번씩 탐색하므로 시간 복잡도는 O(n)입니다.
• 입력 크기가 최대 10,000이므로 충분히 효율적입니다.

---

결과

코드는 전위 순회 입력을 정확히 후위 순회로 변환하며, 재귀적 탐색으로 효율적인 풀이를 제공합니다. 트리 구조의 특징을 활용하여 문제를 효과적으로 해결합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!