[BOJ 2263] 트리의 순회(C++)
트리의 순회 (Gold 3) 문제 전체 문제 보기 2263번: 트리의 순회 첫째 줄에 n(1≤n≤100,000)이 주어진다. 다음 줄에는 인오더를 나타내는 n개의 자연수가 주어지고, 그 다음 줄에는 같은 식으로 포스트오더가 주어진다. www.acmicpc.net 접근법 이 문제는 트리의 중위 순회와 후위 순회 출력 값으로 트리의 전위 순회를 만드는 문제이다. 전위 순회는 루트 노드가 가장 먼저 출력되고, 중위 순회는 루트 노드가 중간에 출력되며, 후위 순회는 루트 노드가 가장 마지막에 출력된다는 특징을 가졌다. 아래의 그래프를 보자. 루트 노드 5가 후위 순회에서 가장 마지막에 출력됨을 알 수 있다. 우리는 이러한 특징을 활용하여 문제를 분할 정복으로 풀 수 있다. 후위 순회의 마지막 값을 루트 노드로 ..
