[백준 5639] 이진검색트리

www.acmicpc.net/problem/5639

5639번: 이진 검색 트리

어렵당...재귀를 사용하는 문제인거까진 알겠는데 접근이 어려웠다.

 

문제에서 요구하는 것은 전위순회를 후위순회로 바꾸는 것이다.

bst이므로 중복된 숫자는 존재하지 않고 왼쪽 서브트리 < 노드 < 오른쪽 서브트리 순으로 값차이가 난다.

 

preorder는 루트 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순이므로 배열의 0번째 인덱스가 무조건 루트임을 확인할 수 있다. 

왼쪽 서브트리에 있는 노드들은 전부 루트보다 값이 작으므로 루트보다 처음으로 큰 값이 등장하면 오른쪽 서브트리의 루트노드인 셈이다.

 

 

따라서 재귀 함수의 구현은

기저 조건: if left > right then return

 

1. 오른쪽 서브트리의 분기 지점을 찾기 mid

2. print right subtree

3. print left subtree

4. print root node 

2,3,4는 post order이다.

 

right subtree를 print하는 재귀함수는 범위를 left+1부터 mid까지로 해준다. 

mid를 찾을 때 주의할점!!! 원래 int mid = left로 두고 arr[mid++] < root를 해주었다. 하지만 그러다 보니 전체 배열 10000칸을 0으로 초기화 시켜서 오른쪽 서브트리가 존재하지 않는 경우 mid가 10000을 초과하여 오버플로우가 발생했다....그래서 right에서 거꾸로 mid를 계산해준다.

 

 

 

//binary search tree
#include <stdio.h>

using namespace std;
int arr[10000];

void recursivePrint(int left, int right)
{
  if (left > right)
  {
    return;
  }

  int root = arr[left];
  int mid = right;
  while (arr[mid] > root)
    mid--;
  recursivePrint(left + 1, mid);
  recursivePrint(mid + 1, right);
  printf("%d\n", root);
}
int main(void)
{
  int i = 0;
  int tmp;
  while (scanf("%d", &tmp) != -1)
  {
    arr[i++] = tmp;
  }
  recursivePrint(0, i - 1);
  return 0;
}