문제

• 
• 시간 제한: 5초
• 메모리 제한: 128MB

Problem Analysis

post에서 node는 각 sub-tree의 root이다. 또한, 해당 node의 In-order에서의 위치를 기준으로, 왼쪽 구간은 left children이고, 오른쪽 구간은 right children이다. 이를 이용해, post-order를 거꾸로 순회하며, 트리를 완성할 수 있다.

Algorithm

Divide and Conquer로, post[idx]를 root로 하는 tree를 In-Order에 대응하는 구간 (l, r)에서 완성한다. 이때, root의 In-Order에서의 위치를 mid라고 할 때, right subtree는 (mid+1, r)에서, left subtree는 (l, mid-1)에서 recursive call을 통해 만든다.

Data Structure

• node: l_child, r_child, nodeNum을 저장하는 struct
• post_order: 각 순번에서의 nodes를 저장
• nodeIdxIn: in-order에서의 node의 index를 저장

결과

Other

시간 복잡도는 O(N)이다.