[BOJ] 5639 - 이진 검색 트리

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

BOJ - 이진 검색 트리

문제 유형: 트리, 재귀, dfs, 이진탐색트리(BST)

문제 난이도: Gold IV

시간 제한: 1초

메모리 제한: 256MB

 

문제

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

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

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

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

 

입력

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

 

출력

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

 

풀이

처음 입력을 받아서 큐에 저장한다. eof까지 큐에 밀어넣으면 된다.)

 

BST의 성질을 이용해서 전위순회를 읽고 트리를 재구성할 수 있다.

왼쪽자식은 자신의 왼쪽자식보다 커야 하고, 부모보다 작아야 한다.

오른쪽자식은 자신의 오른쪽자식보다 작아야 하고, 부모보다 커야 한다.

그래서, 재귀를 다음과 같이 해야 한다: generate(TreeNode* root, queue<int>& q, int left, int right)

  우선, 왼쪽 서브트리를 채워주자.

  만약 큐의 맨 앞이 left ~ root -> key의 사이에 있다면, 왼쪽 서브트리를 확장하러 왼쪽 자식노드를 만들고, 재귀호출한다.

   이때, 다음 호출의 left는 left, right는 root -> key가 되어야 한다.

  그 뒤, 만약 큐의 맨 앞이 root -> key ~ right의 사이에 있다면,  오른쪽 서브트리를 확장하러 오른쪽 자식노드를 만들고, 재귀호출한다.

   이때, 다음 호출의 left는 root -> key, right는 right가 되어야 한다.

 

처음에 있는 큐의 맨앞번호로 루트노드를 만들어주고, 재귀호출하면 된다.

재구성된 트리를 후위순회하여 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

struct TreeNode {
  int key;
  TreeNode *left;
  TreeNode *right;
  TreeNode(int key) {
    this->key = key;
    this->left = NULL;
    this->right = NULL;
  }
};

void generateTree(TreeNode *root, queue<int> &q, int left, int right) {
  if (q.empty())
    return;
  if (root->key > q.front() && q.front() > left) {
    root->left = new TreeNode(q.front());
    q.pop();
    generateTree(root->left, q, left, root->key);
  }
  if (q.empty())
    return;
  if (root->key < q.front() && q.front() < right) {
    root->right = new TreeNode(q.front());
    q.pop();
    generateTree(root->right, q, root->key, right);
  }
}

void postOrder(TreeNode *root) {
  if (!root)
    return;
  postOrder(root->left);
  postOrder(root->right);
  cout << root->key << "\n";
}

int main(int argc, char *argv[]) {
  queue<int> q;
  int temp;
  while (cin >> temp) {
    q.push(temp);
  }

  if (q.empty())
    return 0;

  TreeNode *root = new TreeNode(q.front());
  q.pop();

  TreeNode *p = root;
  generateTree(root, q, INT_MIN, INT_MAX);

  postOrder(root);

  return 0;
}