# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # 트리 순회하기
# 문제 링크: https://www.acmicpc.net/problem/1991
#
# 일단 문제를 열심히 읽었는데 문제는 어렵지 않다. 기본적인 2진트리 순회니까. 
# 문제는 입력부를 가지고 트리를 구성하는게 더 어려운 듯한 느낌이 ㅋ. 
#
# > 첫째 줄에는 이진 트리의 노드의 개수 N(1≤N≤26)이 주어진다. 
# > 둘째 줄부터 N개의 줄에 걸쳐 각 노드와 그의 왼쪽 자식 노드, 오른쪽 자식 노드가 주어진다. 
# > 노드의 이름은 A부터 차례대로 영문자 대문자로 매겨지며, 항상 A가 루트 노드가 된다. 자식 노드가 없는 경우에는 .으로 표현된다.
#
# 먼저 트리부터 만들자.
# 그리고 트리를 순회해서 노드를 찾는 메소드도 만들어야 한다. 
# BST가 아니므로 BST search를 쓸 수 없음에 주의!
# 값을 찾기 위해 중위순회의 변형으로 구현을 해 보았다. 

# +
class TreeNode:
    def __init__(self, value):
        self.value = value
        self.left = self.right = None
    
    # 주어진 문제의 입력을 처리하기 위한 함수
    def insert(self, value, lvalue, rvalue):
        # it always returns a node has value
        node = find(self, value)
        if lvalue != '.':
            node.left = TreeNode(lvalue)
        if rvalue != '.':
            node.right = TreeNode(rvalue)
    
def find(node, value):
    if node is None:
        return
    elif node.value == value:
        return node
    else:
        left = find(node.left, value)
        if left is not None:
            return  left
        right = find(node.right, value)
        return right

def preorder(node, array):
    if node is not None:
        array.append(node.value)
        preorder(node.left, array)
        preorder(node.right, array)

def inorder(node, array):
    if node is not None:
        inorder(node.left, array)
        array.append(node.value)
        inorder(node.right, array)

def postorder(node, array):
    if node is not None:
        postorder(node.left, array)
        postorder(node.right, array)
         array.append(node.value)

root = TreeNode('A')
root.insert('A', 'B', 'C')
root.insert('B', 'D', '.')

print(find(root, 'A').value)
print(find(root, 'B').value)
print(find(root, 'C').value)
print(find(root, 'D').value)
# print(find(root, 'E').value) error
# -

# 이제 주어진 문제의 입력을 처리해 보자.

# +
input_arr='''7
A B C
B D .
C E F
E . .
F . G
D . .
G . .'''.split('\n')

input_len = input_arr[0]
root = TreeNode('A')
for line in input_arr[1:]:
    arr = line.split()
    root.insert(arr[0], arr[1], arr[2])

pre = []
in_arr = []
post = []
preorder(root, pre)
inorder(root, in_arr)
postorder(root, post)


print(''.join(pre))
print(''.join(in_arr))
print(''.join(post))

# -





StarcoderdataJupyterScriptsDedupFiltered