[백준] 트리의 순회

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

2263번: 트리의 순회

stack을 이용하는 문제입니다. 

 

문제부터 간단하게 요약해보면, inorder와 postorder의 배열이 주어지면 이 두개를 사용하여 preorder 배열을 return해야 합니다.

 

<Solution>

사실 이 문제의 해결방법은 대표적으로 두가지가 있을 것 같습니다.

 

1. inorder와 postorder를 이용해 tree를 실제로 구현한 후, 해당 tree를 이용하여 preorder를 return하는 방법

2. tree를 구현하지 않고 inorder와 postorder를 적절히 사용하여 preorder를 return하는 방법

 

이렇게 두가지가 있을 것 같습니다. 

 

다음 두 포스트가 이 문제의 해결방법에 대해 잘 알려주고 있습니다. 

혹시 궁금하신 분들은 참고하면 좋을 것 같습니다.

 

<Tree를 구현하는 방법>

https://www.geeksforgeeks.org/construct-a-binary-tree-from-postorder-and-inorder/

Construct a Binary Tree from Postorder and Inorder - GeeksforGeeks

 

<Tree를 구현하지 않고 해결하는 방법>

https://www.geeksforgeeks.org/preorder-from-inorder-and-postorder-traversals/

Preorder from Inorder and Postorder traversals - GeeksforGeeks

 

제가 푼 방법은 두번째 방법입니다. (Tree를 구현하지 않고 해결하는 방법)

설명을 해보겠습니다. 

 

아이디어의 출발은 

 

Inorder : left, root, right

Postorder : left, right, root

Preorder : root, left, right

 

이 순서에서 출발합니다. 

 

우리는 postorder의 가장 마지막은 항상 root node라는 것을 알고 있습니다. 그렇다면, 이 root node를 이용하면, inorder의 left, right를 분해할 수 있고, 이것을 이용하면 postorder의 left, right를 구분할 수 있습니다. (postorder의 가장 끝은 root인 것을 알지만 left와 right의 경계를 그냥 알수는 없기에 inorder를 활용해야함)

 

그러면 이제 스택을 생각해봅시다. 

 

Postorder를 올바르게 분해한 것을 각각

post_left, post_right, post_root라고 두면, 

stack = [[post_right], [post_left], [post_root]]로 구성을 하면 이것이 [right subtree][left subtree][root]의 구조가 됩니다.

 

이제 stack의 마지막은 post_root로 1개의 root node일 것이므로 pop해서 preorder array에 append합니다. 

stack = [[post_right], [post_left]]

preorder_array = [post_root]

 

이제 post_left(subtree) 또한 postorder traversal의 결과일 것이므로 가장 마지막 element가 해당 subtree의 root가 될 것이고 위의 과정을 recursive 하게 구성하면, preorder array를 구성할 수 있습니다.

 

실제 구현은 아래와 같습니다.

import sys

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

inorder = list(map(int, sys.stdin.readline().rstrip().split()))
postorder = list(map(int, sys.stdin.readline().rstrip().split()))

# inorder : left root right
# postorder : left right root
# preorder : root left right
def div_postorder_inorder_left_right_root(postorder, inorder):
    root = postorder[-1]
    # find index of root in inorder
    idx_root = inorder.index(root)
    
    inorder_left = inorder[:idx_root]
    inorder_right = inorder[idx_root+1:]
    
    return [[postorder[len(inorder_left):-1],inorder_right], [postorder[:len(inorder_left)], inorder_left], [[root], [root]]]
        

stack = [*(div_postorder_inorder_left_right_root(postorder, inorder))]

preorder = []
while(stack):
    p, i = stack.pop()
    if len(p) == 1:
        preorder.append(*p)
    elif len(p) == 0:
        continue
    else:
        for e in div_postorder_inorder_left_right_root(p,i):
            stack.append(e)

print(' '.join(list(map(str,preorder))))