트리 순회 순서 변경 TRAVERSAL

두 가지 순회방법이 나와있을 때, 나머지 순회방법을 구하는 문제다

이 문제는 preorder와 inorder가 주어졌을 때 나머지 postorder를 구하는 문제다

 

먼저 postorder의 순회경로는 왼쪽 자식, 오른쪽 자식, 루트가 되므로 경로를 구한 뒤 다음의 순서대로 출력을 해야한다

가장 중요한 것이 루트와 왼쪽과 오른쪽 자식의 경계를 구해야한다

 

루트는 preorder의 첫번째 원소가 된다. 왼쪽 자식은 inorder에서 루트가 나오기 전까지의 부분이고, 오른쪽 자식은 자연스럽게 루트 이후부터 마지막까지가 된다. 따라서 나눈 부분에 대해서 매개변수로 preorder과 inorder를 넣어서 재귀를 도리면 결국엔 하나만 남았을 때 그것을 출력하면 된다

 

문제: https://algospot.com/judge/problem/read/TRAVERSAL

깃허브주소: https://github.com/surinoel/boj/blob/master/TRAVERSAL.cpp