[python] algospot TRAVERSAL

문제

-> 문제 링크 : https://algospot.com/judge/problem/read/TRAVERSAL

algospot.com :: TRAVERSAL

 

문제풀이

전위 순회식과 중위 순회식을 이용해 후위 순회식을 만드는 코드를 작성해야한다.

순회식에는 각각 특성이 있는데, 전위 순회식은 루트와 왼쪽 서브트리, 오른쪽 서브트리 중 루트를 먼저 방문하고,

중위 순회식은 왼쪽 서브트리를 먼저 방문하고 루트를 방문하게 된다.

 

순회식은 재귀적으로 돌며 매 순간 루트, 왼쪽 서브트리, 오른쪽 서브트리 중 선택하는 부분 문제들로 구성되어 있다.

       x
  y        z
순휘식은 움직이면서 항상 이런 모양의 노드를 만나게 된다. 그러면 전위식은 xyz, 중위식은 yxz, 후위식은 yzx이다.

y와 z밑에 어떤 값들이 있는지 모르니 xy[?]z[?] y[?]xz[?], y[?]z[?]x로 표현이 가능하다.

 

전위식에서는 항상 첫번째 나오는 번호가 루트번호이다.

중위식에서는 항상 루트 번호 왼쪽에 있는 문자열들이 왼쪽 서브트리에 있는 문자들이고,

루트 번호에서 오른쪽에 있는 문자열들은 오른쪽 서브트리에 있는 문자들이 된다.

 

그렇다면 전위식에서 항상 루트의 번호를 찾을 수 있고, 중위식에서는 루트 번호를 이용해 왼쪽, 오른쪽 서브트리를 구할 수 있다.

그리고 문자열의 배치를 후위 순회식처럼 바꿔주면 중위순회식에서 나온 전체 문자열이 후위순회식에서 나온 문자열로 바뀌게 된다.

 

코드

import sys

class Node :
    def __init__(self, val,left,right):
        self.val = val
        self.left = left
        self.right = right


class Tree :
    def __init__(self, pre_list, ins_list):
        self.pres_list = pre_list
        self.ins_list = ins_list
        self.root_idx = 0

    def makePost(self):
        return self.findRoot(self.ins_list)

    def findRoot(self, ins):

        if not ins :
            return ""

        root_num = self.pres_list[self.root_idx]
        self.root_idx += 1
        ins_root_idx = ins.index(root_num)

        left_ins = ins[:ins_root_idx]
        right_ins = ins[ins_root_idx+1:]
    
        left = self.findRoot(left_ins)
        right = self.findRoot(right_ins)

        left = left + " " if left else left
        right = right + " " if right else right

        return left + right + str(root_num)

T = int(sys.stdin.readline().rstrip())

for _ in range(T) :
    N = int(sys.stdin.readline().rstrip())

    pres = list(map(int, sys.stdin.readline().rstrip().split()))
    ins = list(map(int,sys.stdin.readline().rstrip().split()))

    tree = Tree(pres, ins)
    print(tree.makePost())

 

 

코드에 잘못된 부분이나 개선 사항이 있다면 댓글로 알려주시면 감사하겠습니다.