백준 4256 - 트리 (Python)

https://acmicpc.net/problem/4256 

4256번: 트리

2263이 중위와 후위를 전위로 바꾸는 것이었다면, 4256은 전위와 중위를 후위로 바꾸는 문제였다.

index를 기준으로 푸는 것은 2263번 문제와 동일했다.

다시 풀어도 왼쪽 자식 트리와 오른쪽 자식 트리의 길이를 어떻게 나타내야 하는지가 헷갈렸다.

이 문제에서 결국 푸는 데 가장 중요한 단서는 중위 순회식이다. 전위와 후위 표기식에서는 각각 맨 앞, 맨 뒤에 루트가 나오니 그 루트를 중위에서 찾아 자식 노드를 찾기 때문이다. 따라서 기준은 중위 순회식이 되어야 한다.

​