[SWEA / Python ] 1231. [S/W 문제해결 기본] 9일차 - 중위순회

풀이

입력이 노드의 번호, 값, 왼쪽 자식, 오른쪽 자식으로 들어온다.
자식은 입력이 없을 수 있다.

defaultdict를 이용해 트리를 구현했다.
Node 클래스를 선언하고, 자식을 노드의 번호로 지정한다.

dfs를 돌면서 왼쪽 자식을 탐색하고, 문자를 추가하고, 오른쪽 자식을 탐색함으로 중위 순회를 구현했다.

코드

from collections import deque, defaultdict

class Node:

    def __init__(self, data):
        self.data = data
        self.left = None
        self.right = None

def inorder(node):
    global ans
    if node.left:
        inorder(tree[node.left])

    ans += node.data

    if node.right:
        inorder(tree[node.right])



result = []
for case in range(1, 10 + 1):
    ans = ""
    N = int(input())
    tree = defaultdict(Node)

    for _ in range(N):
        arr = list(input().split())
        tree[int(arr[0])] = Node(arr[1])

        if len(arr) > 2:
            tree[int(arr[0])].left = int(arr[2])
            if len(arr) > 3:
                tree[int(arr[0])].right = int(arr[3])


    inorder(tree[1])

    result.append(f"#{case} {ans}")

for r in result:
    print(r)