2263. 트리의 순회

2263번: 트리의 순회

---

트리의 순회 방법에는 크게 세 가지가 있다. 순회 방법을 구분하는 방법은 루트를 언제 방문하는지 구분하는 것이다.

 

1. 전위 순회(preorder): 루트 방문→왼쪽 서브 트리 방문→오른쪽 서브 트리 방문

2. 중위 순회(inorder): 왼쪽 서브 트리 방문→루트 방문→오른쪽 서브 트리 방문

3. 후위 순회(postorder): 왼쪽 서브 트리 방문→오른쪽 서브 트리 방문→루트 방문

 

중위 순회, 후위 순회한 결과가 각각 주어질 때, 전위 순회를 수행해 보자.

---

우리는 중위 순회와 후위 순회로부터 정보를 얻어내야 한다. 트리는 본질적으로 재귀적이기 때문에, 좌우 서브 트리를 구분하면 될 것 같다.

 

중대한 힌트 하나를 제공하고자 한다. 서브 트리를 구분하려면 루트를 알아야 하는데, 루트 노드를 어떻게 찾을 수 있을까? 여기에 대한 고민을 직접 해 보고, 그래도 어렵다면 다음을 읽도록 하자. 

 

스포일러 주의

루트 노드가 가운데에 숨어 있는 중위 순회와 달리, 전위·후위 순회는 루트를 바로 찾을 수 있다. 후위 탐색의 맨 끝에 있는 노드가 루트이다.

 

루트를 찾았으면 이제 좌우 서브 트리를 나눌 수 있다. 중위 순회에서 루트를 기준으로 왼쪽, 오른쪽 부분을 나누면 된다. 서브 트리를 재귀적으로 탐색하면 문제 해결!

 

* 시간 초과가 나는 이유

중위 순회에서 루트를 찾을 때, 단순히 선형 탐색을 하는 것은 좋지 않다. 최악의 경우 O(n) 탐색을 n번 반복하기 때문이다.

 

따라서 트리를 재귀 탐색하기 전에 인덱스를 저장할 필요가 있다. 인덱스 배열을 만들면  노드의 인덱스를 O(1)에 구할 수 있다.

---

보통 이런 건 c++로 푸는데.. 파이썬 한번 써 보고 싶어서.

물론 sys.setrecursionlimit은 해 줘야 한다. ㅋㅋ