[백준 5639] 이진 검색 트리 (C#, C++) - soo:bak

문제 링크

5639번 - 이진 검색 트리

설명

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

접근법

전위 순회에서 첫 번째 값은 항상 루트입니다. 이진 검색 트리의 성질에 따라 루트보다 작은 값들은 왼쪽 서브트리, 루트보다 큰 값들은 오른쪽 서브트리에 속합니다.

전위 순회 배열에서 루트 다음 위치부터 루트보다 큰 값이 처음 나오는 위치를 찾으면 왼쪽과 오른쪽 서브트리의 경계를 알 수 있습니다. 이 경계를 기준으로 왼쪽 구간과 오른쪽 구간에 대해 같은 과정을 재귀적으로 수행합니다.

후위 순회는 왼쪽, 오른쪽, 루트 순서이므로 왼쪽 서브트리를 먼저 처리하고, 오른쪽 서브트리를 처리한 뒤, 마지막에 루트를 출력하면 됩니다.

---

Code

C#

using System;

namespace Solution {
  class Program {
    static int[] pre = new int[10005];
    static int n = 0;

    static void Post(int l, int r) {
      if (l >= r)
        return;
      var root = pre[l];
      var mid = l + 1;
      while (mid < r && pre[mid] < root)
        mid++;
      Post(l + 1, mid);
      Post(mid, r);
      Console.WriteLine(root);
    }

    static void Main(string[] args) {
      string? line;
      while ((line = Console.ReadLine()) != null) {
        if (line.Length == 0)
          continue;
        pre[n++] = int.Parse(line);
      }
      Post(0, n);
    }
  }
}

C++

#include <bits/stdc++.h>
using namespace std;

int pre[10005];
int n = 0;

void post(int l, int r) {
  if (l >= r)
    return;
  int root = pre[l];
  int mid = l + 1;
  while (mid < r && pre[mid] < root)
    mid++;
  post(l + 1, mid);
  post(mid, r);
  cout << root << "\n";
}

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

  while (cin >> pre[n])
    n++;
  post(0, n);

  return 0;
}