4256 트리

이진 트리의 전위 순회와 중위 순회한 결과를 가지고 후위 순회한 결과를 출력하는 문제이다.

이 문제를 풀기 위해선 전위 순회한 결과와 중위 순회한 결과의 성질을 눈치채야 한다.
이 부분은 설명이 복잡하니 예를들어 설명하자면,
전위 순회 : 3 6 5 4 8 7 1 2
중위 순회 : 5 6 8 4 3 1 2 7

전위 순회는 시작부터 결과를 출력하기 때문에 맨 처음 나온 숫자는 루트노드가 된다.
그 노드를 중위 순회한 결과에서 찾아보면, 5번째에 위치한다는 것을 알 수 있다.
중위 순회의 성질을 잘 생각해보면, 루트노드 앞에 나온 결과는 전부 루트노드의 left, 뒤에 나온 결과는 right 자식이다.

위에 나온 결과로 보아 루트노드(3)의 왼쪽 자식은 4개, 오른쪽 자식은 3개이다.
이것은 전위 순회에도 찾아볼 수 있는데, 루트노드의 다음 4개가 왼쪽 자식이고, 그 다음 3개가 오른쪽 자식이 된다.

이것은 루트노드에서만 해당되는것이 아니라 자식에도 적용이 가능하다.
루트의 왼쪽 으로 가보면, 전위 순회의 루트 다음 숫자가 6이기 때문에 6이 루트노드의 왼쪽 자식노드이다.  중위 순회에서 6을 찾아주면 두번째에 있게 되는데, 여기서도 앞에있는 5는 6의 왼쪽 자식이고, 뒤에있는 8 4는 오른쪽 자식이 된다. 이런 과정을 왼쪽으로부터 오른쪽 까지 재귀하면서 마지막에 결과를 출력해주면 후위순위한 결과가 된다.

소스