트리. [2263]

[1. 문제 설명]

n개의 정점을 갖는 이진 트리의 정점에 1부터 n까지의 번호가 중복 없이 매겨져 있다.

이와 같은 이진 트리의 중위 순회와 후위 순회가 주어졌을 때,

전위 순회를 구한다.

 

 

[2. 풀이 접근]

각 순회를 보면 트리의 대략적인 구조를 알 수 있다.

 

중위 순회: [.... Left sub tree...] Root [.... Right sub tree....]

 

후위 순회: [.... Left sub tree...] [.... Right sub tree....] Root

 

후위 순회의 마지막 원소는 전체 tree 의 root 임을 알 수 있다.

이렇게 알아낸 root 를 통해 중위 순회에서 해당 root 의 left sub tree 와 right sub tree 를 알 수 있다.

 

이제, Left sub tree 와 Right sub tree 역시 위와 같은 방식으로 접근 할 수 있다.

 

중위 순회의 Left sub tree 와

후위 순회의 Right sub tree 를 전체 문제 중 하나의 부분문제로 바라볼 수 있기 때문이다.

 

===== 성능 개선 =====

위 접근으로도 제한 시간내 풀이가 가능하지만,

시간을 더 단축 할 수 있다.

 

먼저, 위 접근에서 시간이 걸리는 부분은 중위 순회에서 root 위치를 찾는 것 이다.

탐색 시간은 O(N) 이 걸리는데, 이 시간을 O(1) 으로 줄일 수 있다.

 

table[value] = index 가 되도록 중위 순회에 관한 테이블을 만들어 내면 된다.

 

그러나, table 에 적힌 index 는 절대 위치를 반환하기 때문에,

각 sub tree 들의 부분 문제에서 해당 index 를 바로 사용 할 수 없다.

 

ex) 전체 tree 에서 중위 순회의 right sub tree 가 index: 8 부터 시작한다고 했을 때

이 sub tree 의 부분 문제에서는 index 가 0으로 바뀐다.

 

따라서, index 사용 시 상대적인 값으로 변경해주어야 하고,

이에 필요 한 추가 데이터를 함수로 전달해주어야 한다.

 

 

[3. 코드 - 성능 개선 전]

 

 

[3. 코드 - 성능 개선 후]