득이공간
[백준 C++] 5639 이진 검색 트리 - 트리 본문
#include <iostream>
using namespace std;
int Tree[10001];
void DFS(int Current, int End)
{
if (Current > End)
{
return;
}
int Mid = End + 1;
for (int i = Current + 1; i <= End; ++i)
{
if (Tree[i] > Tree[Current])
{
Mid = i;
break;
}
}
DFS(Current + 1, Mid - 1);
DFS(Mid, End);
cout << Tree[Current] << '\n';
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
int i = 0;
while (true) { cin >> Tree[i]; if (Tree[i] == 0) break; ++i; }
DFS(0, i - 1);
}
이진 트리 문제입니다.
전위 순회 결과가 입력으로 주어지기 때문에
첫 입력인 루트 노드를 기준으로 왼쪽 서브 트리가 쭉 입력되다가
루트 노드보다 큰 값이 나오면,
그때 부터 쭉 오른쪽 서브 트리가 입력되는 것을 알 수 있습니다.
이런식으로 재귀로 왼쪽, 오른쪽 서브 트리를 깊이 우선 탐색해준 다음,
빠져나오면서 각 노드를 출력해주면 후위 순회한 결과를 도출할 수 있습니다.
'PS > 알고리즘 문제풀이' 카테고리의 다른 글
[백준 C++] 15686 치킨 배달 - 브루트포스 (0) | 2024.03.03 |
---|---|
[백준 C++] 12865 평범한 배낭 - 다이나믹프로그래밍 (0) | 2024.03.03 |
[백준 C++] 2096 내려가기 - 다이나믹프로그래밍 (0) | 2024.02.29 |
[백준 C++] 4386 별자리 만들기 - 최소신장트리 (1) | 2024.02.28 |
[백준 C++] 2623 음악프로그램 - 위상정렬 (0) | 2024.02.28 |