[백준] 4256 트리

April 13, 2021 ( last updated : April 13, 2021 )
분할정복 재귀 트리

https://github.com/sneakstarberry/

Abstract

[백준] 4256번 트리

[백준] 4256번 트리

백준 4256번

알고리즘 유형

문제 이해

중위 순회와 전위 순를 한 값이 있을 때 전위 순회 값들을 구해라.

풀이방법

이전에 풀었던 유형과 비슷한데 이진트리는 중앙 루트 노드를 기준으로 양쪽이 서로 나뉩니다. 그리고 나뉜 트리의 가장 윗 쪽 노드를 새로운 루트 노트라고 가정하게 되면 새로운 이진 트리를 구성할 수 있습니다. 새로운 루트가 될 노드를 알 수 있는 방법은 중위 순회를 통해서 알 수 있습니다. 그리고 첫 루트 노드는 전위 순회를 통해서 알 수 있습니다.

#include <algorithm>
#include <iostream>

using namespace std;

int n;
int PRE[1001], IN[1001];

void post(int s, int e, int r) {
  for (int i = s; i < e; ++i) {
    if (IN[i] == PRE[r]) {
      post(s, i, r + 1);
      post(i + 1, e, r + 1 + i - s);
      cout << PRE[r] << ' ';
    }
  }
}

int main() {
  ios::sync_with_stdio(false);
  int t;
  cin >> t;
  while (t--) {
    cin >> n;
    for (int i = 0; i < n; ++i)
      cin >> PRE[i];
    for (int i = 0; i < n; ++i)
      cin >> IN[i];

    post(0, n, 0);
    cout << '\n';
  }
  return 0;
}

Originally published April 13, 2021
Latest update April 13, 2021

Related posts :

{# #}