[대표 유형] 트리 후위 순회

문제 설명

1번 노드를 루트 노드로 하는 이진 트리(Binary Tree) 정보인 childNodes가 매개변수로 주어집니다. 해당 이진 트리에 대해 후위(Postorder) 순회하고, 방문한 순서대로 노드 번호를 반환하는 solution 함수를 작성하시오.

개념 설명

트리 순회(Tree Traversal)는 이진 트리(Binary Tree)에서 정의되는 그래프 순회 방법입니다.
먼저 이진 트리는 모든 내부 노드 들이 둘 이하의 자식 노드를 갖는 트리를 말합니다. 이진 트리의 경우 왼쪽 자식 노드와 오른쪽 자식 노드를 구분하기도 합니다.

트리 순회 중 후위 순회(Postorder Traverse)는 다음과 같은 순서로 트리 순회를 진행합니다.

1. 왼쪽 자식 부분 트리를 재귀적으로 후위 순회합니다.
2. 오른쪽 자식 부분 트리를 재귀적으로 후위 순회합니다.
3. 루트 노드를 탐색합니다.

아래와 같은 이진 트리가 있다고 가정합니다.

루트 노드인 1번 노드에서 후위 순회를 시작합니다.

후위 순회는 자기 자신의 노드를 탐색하기 이전에 왼쪽과 오른쪽 자식 부분 트리를 먼저 순회합니다. 이 때문에 1번 노드를 탐색하기 이전에 2번 노드의 부분 트리를 먼저 순회합니다.

위와 동일한 이유로 5번 노드의 부분 트리를 순회합니다.

5번 노드는 왼쪽 자식 노드가 없기 때문에 왼쪽 자식 부분 트리 순회를 종료합니다.

이후 5번 노드의 오른쪽 자식 부분 트리인 4번 노드의 부분 트리를 순회합니다. 하지만 4번 노드는 자식 노드가 없기 때문에 바로 자기 자신을 탐색하고 순회를 종료합니다.

이렇게 양쪽 자식 부분 트리의 순회를 마친 5번 노드도 자기 자신을 탐색하고 순회를 종료합니다.

2번 노드 관점에서 왼쪽 자식 부분 트리의 순회가 종료되면 오른쪽 자식 부분 트리인 7번 노드 부분 트리의 순회를 시작합니다.

동일한 원리로 6번 노드, 8번 노드의 부분 트리 순회를 시작합니다. 8번 노드는 자식 노드가 없기 때문에 자기 자신을 탐색한 뒤 순회를 종료합니다.

자식 노드 부분 트리를 모두 순회한 6번 노드가 탐색 된 뒤에는 7번 노드의 오른쪽 자식 부분 트리를 순회하고자 하지만 7번 노드는 오른쪽 자식이 없습니다.

이로 인해 7번 노드가 탐색 되고 2번 노드도 차례대로 탐색 됩니다.

1번 노드의 왼쪽 자식 부분 트리가 순회를 종료했으므로 오른쪽 자식 부분 트리인 3번 노드가 탐색되고 마지막으로 1번 노드가 탐색 되면서 후위 순회를 종료합니다.

따라서 주어진 예시에서 후위 순회를 하는 순서는 4 $\rightarrow$ 5 $\rightarrow$ 8 $\rightarrow$ 6 $\rightarrow$ 7 $\rightarrow$ 2 $\rightarrow$ 3 $\rightarrow$ 1 입니다.

제한 사항

• childNodes는 각 노드의 왼쪽과 오른쪽 자식 노드 정보를 담는 이차원 배열입니다.
  • 배열의 길이는 2 이상 100,000 이하입니다.
  • childNodes[i - 1]는 i번 노드의 왼쪽과 오른쪽 자식 노드의 번호를 담은 배열입니다.
    • childNodes[i - 1][0]은 i번 노드의 왼쪽 자식 번호를 의미합니다.
    • childNodes[i - 1][1]은 i번 노드의 오른쪽 자식 번호를 의미합니다.
    • 만일 왼쪽 또는 오른쪽 자식 노드가 없다면 해당 노드 번호는 -1로 표기됩니다.

예시 테스트케이스 설명

1번 테스트케이스 설명

• 개념 설명에서 제시된 예시와 동일합니다.

2번 테스트케이스 설명

• 후위 순회 결과는 아래와 같습니다.
  4 $\rightarrow$ 8 $\rightarrow$ 10 $\rightarrow$ 2 $\rightarrow$ 7 $\rightarrow$ 5 $\rightarrow$ 3 $\rightarrow$ 9 $\rightarrow$ 6 $\rightarrow$ 1

3번 테스트케이스 설명

• 후위 순회 결과는 아래와 같습니다.
  3 $\rightarrow$ 2 $\rightarrow$ 4 $\rightarrow$ 5 $\rightarrow$ 1