python 백준 2263 트리의 순회

https://www.acmicpc.net/problem/2263

tree 만들기

• postorder의 마지막이 root인 것을 이용
• root를 구한 뒤 inorder에서 root를 기준으로 좌우를 가름
  • 갈랐을 때 왼쪽이면 왼쪽 서브 트리, 오른쪽이면 오른쪽 서브 트리
• 왼쪽 서브 트리에 해당하는 postorder 부분을 추출후 그안에서 root 찾기 반복
  • 서브 트리자체를 인자로 함수 재귀 시도
    • 메모리 초과
  • 서브 트리에 해당하는 index의 시작과 끝을 인자로 재귀 시도
    • 파이썬 재귀 한도에 걸려 Recursion Err
    • 인덱스를 list에 추가하면서 pop 하는 형식으로 구현
    • index 시작, 끝 부분을 변수 하나로 바꾼뒤 코드를 짜면 가독성이 좋았을 것 같다

preorder

• 마찬가지로 Recursion Err가 발생 할것 같아 stack 이용
• 루트 => 좌 => 우 순서
• 루트를 먼저 출력 후 좌 => 우 순서로 가야 하므로 stack(선입 후출)에 우=>좌 순으로 추가 하는 형식

def make_tree(index1,index2):
    stack = [((index1),(index2))]
    while stack:
        in_index,post_index=stack.pop()
        root = postorder[post_index[1]-1]
        tree[root] = []
        if in_index[1]-in_index[0] == 1:
            continue
        i = index[root]
        if in_index[0] != i:
            l_root = postorder[post_index[0]+i-in_index[0]-1]
            stack.append(((in_index[0],i),(post_index[0],post_index[0]+i-in_index[0])))
            tree[root].append(l_root)
        else:
            tree[root].append(0)
        if i+1 != in_index[1]:
            r_root = postorder[post_index[1]-2]
            stack.append(((i+1,in_index[1]),(post_index[0]+i-in_index[0],post_index[1]-1)))
            tree[root].append(r_root)
        else:
            tree[root].append(0)

def preorder(root):
    stack = [root]
    while stack:
        now = stack.pop()
        print(now,end=' ')
        if tree[now]:
            if tree[now][1]:
                stack.append(tree[now][1])
            if tree[now][0]:
                stack.append(tree[now][0])

n = int(input())
inorder = list(map(int,input().split()))
postorder = list(map(int,input().split()))
index = {}
for i in range(n):
    index[inorder[i]] = i

start = postorder[-1]
tree = {}
make_tree((0,n),(0,n))
preorder(postorder[-1])