4256. 트리 (Python)

4256번: 트리

 

풀이

 각 순회의 특징을 파악하여 문제를 해결하면 된다. 전위 순회는 부모 노드가 자식 노드의 앞에 출력되고 중위 순회는 부모 노드가 왼쪽 자식 노드와 오른쪽 자식 노드 사이에서 출력된다. 그렇기 때문에 전위 순회 결과의 앞부분을 기준으로 중위 순회 결과에서 재귀 함수를 사용하여 왼쪽과 오른쪽을 하나의 노드가 남을 때까지 쪼개주고 마지막에 출력 작업이 이뤄지도록 하면 된다.

 

 문제의 예제를 통해 살펴보면 다음과 같다. 

 

 위와 같이 재귀 함수는 다음과 같은 순서로 진행되고 이를 통해 트리의 후위 순회 결과를 얻을 수 있다.

1. 왼쪽 자식 노드 탐색 (하나의 노드만 남게 되면 출력)
2. 오른쪽 자식 노드 탐색 (하나의 노드만 남게 되면 출력)
3. 부모 노드 출력 

 

코드

def solve(treeNodes):
    global preorderIdx

    if len(treeNodes) <= 1:
        if len(treeNodes) == 1:  # 현재 노드 리스트의 길이가 1일 경우 해당 노드를 출력하고 종료
            print(treeNodes[0], end=' ')
            preorderIdx += 1
        return  # 노드 리스트가 비어 있으면 아무 작업 없이 종료

    preorderIdx += 1  # 전위 순회에서 찾을 부모 노드 인덱스

    # 중위 순회에서 부모 노드의 인덱스를 찾아
    # 해당 부모 노드를 기준으로 왼쪽 자식 노드들과 오른쪽 자식 노드들로 나뉜다.
    midIdx = treeNodes.index(preorder[preorderIdx])

    # 왼쪽 자식 노드 탐색
    solve(treeNodes[:midIdx])

    # 오른쪽 자식 노드 탐색
    solve(treeNodes[midIdx+1:])

    # 마지막에 부모 노드 출력
    print(treeNodes[midIdx], end=' ')


if __name__ == '__main__':
    T = int(input())

    for _ in range(T):
        N = int(input())  # 노드의 개수
        preorder = list(map(int, input().split()))  # 전위 순회 결과
        inorder = list(map(int, input().split()))  # 중위 순회 결과
        preorderIdx = -1  # 전위 순회에서의 부모 노드 인덱스

        solve(inorder)
        print()