[BAEKJOON]백준 4256번 트리 - 트리(Tree) 자료구조, 분할 정복(Divide and Conquer)

백준 4256번 트리

백준 4256번 트리

설명

전위 순회는 가운데, 왼쪽, 오른쪽으로 가기 때문에 첫번째 값이 가운데 노드이므로 이 노드를 중위 순회에 적용하여 중위 순회를 가운데 노드 기준으로 왼쪽, 오른쪽으로 나누는 분할 정복 형태로 문제를 풉니다. 이렇게 트리를 만들고, 후위 순회로 찍어줍니다.

코드

import sys
from typing import List
input = sys.stdin.readline

# 트리 구조체 선언
class TreeNode:
    def __init__(self, x, left=None, right=None):
        self.x = x
        self.left = left
        self.right = right 


class Solution:
    def tree(self, preorder: List[int], inorder: List[int]):

        # 후위 순회를 찍는 함수
        def print_postorder(node):
            if node.left:
                print_postorder(node.left)
            if node.right:
                print_postorder(node.right)
            print(node.x, end=' ')

        if inorder:

            """전위 순회의 첫번 째 수가 루트이기 때문에
            중위 순회에서 왼쪽 노드, 오른쪽 노드를 가르는 역할을 함
            전위 순회의 첫번 째를 pop하고, 중위 순회에서 그 수의 인덱스를 뽑아냄"""
            index = inorder.index(preorder.pop(0))

            """위에서 뽑은 인덱스의 값으로 TreeNode 객체 생성
            그 값 기준 왼쪽, 오른쪽으로 inorder를 재정의해서 재귀함수 호출"""
            node = TreeNode(inorder[index])
            node.left = self.tree(preorder, inorder[0:index])
            node.right = self.tree(preorder, inorder[index+1:])

            # node 객체로 print_postorder 함수 호출
            return print_postorder(node)


for _ in range(int(input())):
    n = int(input())
    preorder = list(map(int, input().split()))
    inorder = list(map(int, input().split()))
    Solution().tree(preorder, inorder)
    print()