궤도

문제 풀이 inorder는 (왼쪽 트리)(루트)(오른쪽 트리) 순서로 탐색한다. postorder는 (왼쪽 트리)(오른쪽 트리)(루트) 순서로 탐색한다. 1991번의 이 트리를 숫자로 바꿔보자. inorder 순회는 4 2 1 5 3 6 7 이고 postorder 순회는 4 2 5 7 6 3 1 이다. postorder 순회의 맨 마지막 값인 1(=A)가 트리의 최상위 root 노드인 것을 확인할 수 있다. 1을 기준으로 inorder를 나눠보면 (4 2)(1)(5 3 6 7)이 된다. 4(=D), 2(=B)는 A의 왼쪽 트리 요소이고, 5(=E), 3(=C), 6(=F), 7(=G)는 A의 오른쪽 트리 요소다. 루트노드를 기준으로 왼쪽, 오른쪽 트리로 분할해나가며 트리를 구하면 된다. 사실 preord..