[자료구조] 이진 검색 트리(5639)

 

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

5639번: 이진 검색 트리

 

 

1. 문제 개요

 

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 문제.

 

이진 검색 트리란, 노드의 왼쪽 서브트리에 있는 모든 노드의 키가 노드의 키보다 작고 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크며, 왼쪽, 오른쪽 서브트리도 이진 검색 트리인 이진 트리를 말한다.

 

전위 순회는 루트-왼쪽-오른쪽 순으로 노드를 방문

후위 순회는 왼쪽-오른쪽-루트 순으로 노드를 방문한다.

 

 

 

2. 입출력

 

 

3. 문제 풀이

 

처음에는 트리 구현을 통해서 입력이 들어올 때 트리 안에 값을 넣고 트리를 후위 순회로 탐색하며 출력하면 된다고 생각했다.

하지만 트리 구현이 미숙했던 탓인지 낮은 퍼센티지에서 틀렸습니다가 떴다.

 

결국 구글링으로 다른 접근법을 찾아보던 중 굳이 트리를 구현하지 않아도 전위 순회와 후위 순회의 특성을 이용하는 것만으로도 문제를 해결할 수 있다는 걸 깨달았다.

 

인풋 값을 일차원 배열에 저장하고 전위 순회가 root -> left -> right 순으로 방문한다는 사실을 활용해서 일차원 배열 안의 값을 재귀로 방문하기만 하면 문제가 굉장히 쉬워진다.

 

 

4. 전체 코드

 

#include <iostream>
#include <vector>


using namespace std;
//0<= node <=10000
//전위 순회: root -> left -> right 50 / 30 / 24 / 5 28 / 45 / 98 / 52 / 60
//후위 순회: left -> right -> root 5 28 24 45 30 60 52 98 50 이다.


int tree[10000];
void postOrder(int start, int end)
{
    if (start >= end) return;
    if (start == end - 1) {
        cout << tree[start] << '\n';
        return;
    }
    
    int idx = start + 1;
    while (idx<end)
    {
        if (tree[start]<tree[idx]) break;
        idx++;
    }
    
  
    postOrder(start+1, idx); //left
    postOrder(idx, end); //right
    cout << tree[start] << '\n'; //root
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    
    int temp;
    int num = 0;
    while (cin >> temp) { //입력이 들어올 때까지 받음
        tree[num++] = temp;
    }


    postOrder(0,num);
    
    return 0;
}

 

이진 검색 트리 특성상 왼쪽 서브 트리에는 루트 노드보다 작은 값을 갖는 노드가 존재하고 오른쪽 서브 트리에는 루트 노드보다 큰 값을 갖는 노드가 존재하므로 재귀를 통해 루트 노드보다 값이 커지는 지점을 찾아내어 다시 재귀로 그 지점을 탐색하면 손쉽게 정답을 출력할 수 있다.

 

아직 재귀함수가 익숙하지 않아 재귀를 사용한 접근법을 나 스스로 찾아내기는 쉽지 않았다. 재귀함수는 연습이 더 필요할 것 같다.