[트리] 알고스팟 TRAVERSAL
https://www.algospot.com/judge/problem/read/TRAVERSAL
// 교재 p.686
// 21.3 문제: 트리 순회 순서 변경 (문제 ID: TRAVERSAL, 난이도: 하)
// correct: TRAVERSAL
/*
책 보고 힌트 얻고 풀었음.
아이디어: preOrder는 루트 먼저니까 inorder에서 preOrder 값을 찾으면 왼쪽 서브트리, 오른쪽 서브트리로 나눌 수 있다.
이를 이용하여 재귀적으로 왼쪽, 오른쪽, 가운데 순으로 보면서 출력
- 자신의 접근 되새겨보기
하나도 모르겠어서 그냥 책을 봤다. - 자신이 왜 이 풀이를 떠올리지 못했는지 살펴보기
1. divide and conquer가 잘 안 되었다.
2. preOrder, inOrder의 특징을 잘 되새겨 봤어야 했다.
3. 트리니까 재귀적으로 뭔가를 할 수 있다는 걸 느껴야 했다.
4. 재귀적으로 할 수 있다는 것은 작은 비슷한 문제로 쪼갤 수 있다는 뜻이다.
*/
#include <stdio.h>
#include <iostream>
using namespace std;
int C; // 테스트 케이스 수
int N; // 트리에 포함된 노드의 수
int preOrder[100];
int inOrder[100];
int postOrder[100];
// preOrder 훑는 인덱스
int preIndex = 0;
// first는 해당하는 처음 인덱스
// last는 해당되는 마지막 인덱스 +1
void printPostOrder(int first, int last)
{
// 기저: 비었으면 리턴
if ( (last - first) == 0)
{
// cout<<"리턴"<<endl;
return;
}
// 프리에서 차례대로 하나씩 빼옴
int now = preOrder[preIndex++];
// now를 inOrder에서 몇 번쨰 인덱스인지 찾음
int inOrderIdx;
for (int i = first; i < last; i++)
{
if (inOrder[i] == now)
{
inOrderIdx = i;
break;
}
}
// 포스트 오더에 맞게 출력
// 왼쪽 서브트리
printPostOrder(first, inOrderIdx);
// 오른쪽 서브트리
printPostOrder(inOrderIdx+1, last);
// 빼온거 출력
printf("%d ", now);
}
int main()
{
scanf("%d", &C);
for (int i = 0; i < C; i++)
{
scanf("%d", &N);
// cout<<"프리"<<endl;
for (int j = 0; j<N; j++)
{
scanf("%d", &preOrder[j]);
}
// cout<<"인"<<endl;
for (int j = 0; j<N; j++)
{
scanf("%d", &inOrder[j]);
}
// preOrder 훑는거 초기화
preIndex = 0;
printPostOrder(0, N);
printf("\n");
}
// cout<<"끝"<<endl;
}
Author And Source
이 문제에 관하여([트리] 알고스팟 TRAVERSAL), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ember/알고스팟-TRAVERSAL저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)