[백준BOJ] 5639번: 이진 검색 트리 (cpp / c++)

Description 

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

• 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.
• 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.
• 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

 

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

 

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

입출력 예

50 30 24 5 28 45 98 52 60

5 28 24 45 30 60 52 98 50

 

권장 시간 복잡도 $O(Nlog(N))$

---

 

풀이

#include <iostream>
#include <vector>

using namespace std;

class Node;
vector<Node> nodeList;

class Node {
  public:
    int num;
    int leftChild = -1;
    int rightChild = -1;
    Node(int n) : num(n) {}
};

void insert(int node, int num) {
  if (num > nodeList[node].num) {
    if (nodeList[node].rightChild == -1) {
      nodeList.emplace_back(Node(num));
      nodeList[node].rightChild = nodeList.size() - 1;
    } else {
      insert(nodeList[node].rightChild, num);
    }
  } else {
    if (nodeList[node].leftChild == -1) {
      nodeList.emplace_back(Node(num));
      nodeList[node].leftChild = nodeList.size() - 1;
    } else {
      insert(nodeList[node].leftChild, num);
    }
  }
}

void postorder(int n) {
  if (nodeList[n].leftChild != -1) postorder(nodeList[n].leftChild);
  if (nodeList[n].rightChild != -1) postorder(nodeList[n].rightChild);
  cout << nodeList[n].num << "\n";
}

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

  int rootNum;
  cin >> rootNum;
  nodeList.emplace_back(Node(rootNum));

  int input;
  while (cin >> input) {
    insert(0, input);
  }
  
  postorder(0);
  return 0;
}

 

(풀이전략) 추후 추가 예정 / 이 방식은 시간 복잡도가 $O(log(N))$에서 $O(N^2)$까지 오가는 방식이지만 분할 정복으로 BST를 build하지 않고도 풀 수 있다고 한다.

---

 

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