devbelly

문제 www.acmicpc.net/problem/2263 알고리즘 재귀 풀이 트리의 인오더, 포스트오더가 주어질 때, 프리오더를 출력하는 문제입니다. 포스트오더는 배치가 왼쪽 서브트리 포스트오더 출력 + 오른쪽 서브트리 포스트오더 출력 + 루트 입니다. 즉 맨 오른쪽 값이 루트임을 알 수 있습니다. 인오더의 배치는 왼쪽 서브트리 인오더 출력 + 루트 + 오른쪽 서브트리 인오더 출력입니다. 포스트오더에서 루트를 파악했다면 인오더에서 해당 루트의 위치를 찾아 왼쪽 서브트리와 오른쪽 서브트리를 나누어줍니다. 인오더와 포스트오더의 서브트리의 크기는 일치하므로 인오더에서 찾은 서브트리크기를 통해 포스트오더의 구간을 나누어 재귀호출하면 풀 수 있습니다. 코드 #include #define rep(i, n) for ..