이진 검색 트리의 전위 순회 값이 주어졌을 때 후위 순회 값을 출력하는 문제입니다. 이 문제는 주어진 전위 순회 값에서 각 노드의 왼쪽 서브트리와 오른쪽 서브트리에 해당하는 부분이 어디인지만 구할 수 있다면 풀 수 있는 문제입니다.
여기서 주어진 이진 검색 트리는 트리이기는 한데 노드의 왼쪽 서브트리에 있는 노드는 원래 노드보다 키 값이 작고 오른쪽 서브트리는 키 값이 큽니다. 그런데 주어진 것이 전위 순회라고 했으므로 5 1 4 2 7 8이라고 주어지면 5보다 작은 1 4 2가 왼쪽 서브트리, 7 8이 오른쪽 서브트리의 전위 순회값임을 알 수 있습니다. 그런데 서브트리 또한 이진 검색 트리이므로 각 서브트리에 대해서 루트와 그 서브트리로 분리하여 트리의 구조를 파악한 뒤, 그 구조에 따라 후위 순회값을 알맞게 출력하면 됩니다.
PS알못 OrbitHv의 PS