백준 1991. 트리 순 (Python)

Wjong·2023년 2월 20일
0

baekjoon

목록 보기
2/17

문제 https://www.acmicpc.net/problem/1991

풀이

이진트리를 입력받아 전위순회(preorder), 중위순회(inorder), 후위순회(postorder)를 구현하는 문제이다.
처음에 트리의 입력이 노드순서대로 입력되는줄 알았는데 아니여서 개고생 ㅠㅠ
트리의 순서가 무작위로 입력되므로 이를 tree배열에 잘 넣어주어야 한다.

  • t,l,r을 입력받는다
  • t를 인덱스로 변환시킨다(A -> ord(A)-64 -> 1번인덱스)(트리는 인덱스1시작이 편하드라..)
  • tree, left_tree, right_tree에 변환된 인덱스위치에 t, l, r값을 넣어준다.

모두 입력받았으면 전위, 중위, 후위순회 진행!
재귀함수로 진행한다.
전위순회 : root -> left -> right
중위순회 : left -> root -> right
후위순위 : left -> right -> root

N=int(input())
tree=[0]*(N+1)
left_tree=[0]*(N+1)
right_tree=[0]*(N+1)

for i in range(1,N+1):
    t,l,r=map(str,input().split())
    tree[ord(t)-64]=t
    left_tree[ord(t)-64]=ord(l)-64 if l!="." else "."
    right_tree[ord(t)-64]=ord(r)-64 if r!="." else "."
def preorder(x):
    res=tree[x]
    if left_tree[x]!=".":res+=preorder(left_tree[x])
    if right_tree[x]!=".":res+=preorder(right_tree[x])
    return res    

def inorder(x):
    res=""
    if left_tree[x]!=".":res+=inorder(left_tree[x])
    res+=tree[x]
    if right_tree[x]!=".":res+=inorder(right_tree[x])
    return res    
def postorder(x):
    res=""
    if left_tree[x]!=".":res+=postorder(left_tree[x])
    if right_tree[x]!=".":res+=postorder(right_tree[x])
    res+=tree[x]
    return res    

print(preorder(1))
print(inorder(1))
print(postorder(1))
profile
뉴비

0개의 댓글