백준 2263. 트리의 순회

https://www.acmicpc.net/problem/2263

2263번: 트리의 순회

 

트리를 순회하는 3가지 방법, preOrder, inOrder, postOrder에 대해서 더 자세히 생각해본 좋은 문제였다.

 

문제에서 주어지는건 이진트리의 inOrder와 postOrder의 결과이다.

postOrder: Left -> Right -> Root 

따라서 postOrder에서 마지막에 오는 노드가 루트노드다.

 

inOrder: Left -> Root -> Right 

따라서 inOrder 에서 루트 노드 기준으로 왼쪽에 있는 노드들이 left child, 오른쪽에 있는 노드들이 right child 다.

 

이 법칙에 따라 postOrder의 left child 부분, right child 부분

inOrder의 left child 부분, right child 부분 을 나눠서 재귀적으로 함수를 만들면 된다.

이 과정에서 postOrder의 마지막 부분이 항상 루트이기 때문에 루트값을 출력 -> left child -> right child 순으로 호출하면 자연스럽게 preOrder가 된다.