[백준] 이진 검색 트리

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

5639번: 이진 검색 트리

트리 자료구조를 이용하고, dfs 또는 재귀를 사용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

이진 검색트리를 preorder traversal한 결과가 주어질 때, 이 이진 검색트리를 postorder traversal한 결과를 return 해야 합니다.

 

<Solution>

사실 이 문제는 이전에 포스팅 했던 

https://life318.tistory.com/80

[백준] 트리의 순회

이 문제와 굉장히 비슷합니다. 

 

위의 문제에서는 inorder와 postorder의 결과를 통해 preorder결과를 return해야 하는 문제였습니다. 하지만 이 문제에서는 조건이 마치 하나처럼 보입니다. 하지만 잘 생각해보면, 문제에서 "이진 검색 트리" 라는 조건을 준 이것이 element를 가장 작은것에서 큰것 순서로 나열한 것이 inorder traversal의 결과 임을 알 수 있습니다. 

(즉 preorder traversal의 결과를 sorting 한 결과가 inorder traversal의 결과임!!!)

 

따라서 우리는 이 문제를 inorder와 preorder의 결과를 통해 postorder를 만들어 내는 문제라고 바꿀 수 있습니다. 

 

이제 생각을 다시 해봅시다. 

inorder : left root right preorder : root left right

이므로 postorder인 left, right, root는 

1. preorder의 가장 첫째 값은 root이다.
2. 이 root값의 index를 inorder에서 찾으면 inorder에서 left와 right를 구분이 가능하다
3. 2번과정에서 구분한 left와 right로 preorder의 left와 right도 구분이 가능하다.
4. 이렇게 구분한 root, left, right를 postorder의 순서에 맞게 둔다음 해당하는 left right subtree에 대해 같은 1~3번 과정을 반복

위의 과정을 통해 해결할 수 있습니다. 

 

이제 실제 구현을 살펴봅시다. 

가장 처음에는 재귀함수를 이용하여 편하게 구현하려고 시도하였습니다. 하지만 재귀의 깊이가 생각보다 깊어져서 처음에는 recursion error가 발생하더니 recursion limit을 푸니 메모리초과가 나왔습니다. (재귀는 stack이 계속 쌓이는 것이므로 메모리 초과가능성이 충분함)

위의 과정에 해당하는 코드는 다음과 같습니다. 혹시나 재귀로 구현하는 분들은 코드 스타일정도만 참고하시면 될 것 같습니다. 

import sys
sys.setrecursionlimit(10**6)
preorder = []

while(1):
    string_ = sys.stdin.readline().rstrip()
    if string_ == '':
        break
    preorder.append(int(string_))

inorder = preorder[:]
inorder.sort()

def build_postorder(preorder, inorder):
    # print(f'preorder, inorder = {preorder, inorder}')
    if len(preorder) == 1:
        return preorder
    if len(preorder) == 0:
        return []

    root = preorder[0]
    idx = inorder.index(root)

    return build_postorder(preorder[1:1+idx], inorder[:idx]) + build_postorder(preorder[1+idx:], inorder[idx+1:]) + [root]

ans = build_postorder(preorder, inorder)
for e in ans:
    print(e)

 

따라서 재귀함수란 dfs의 과정과 동일하므로 재귀함수를 사용하지 않고 stack을 이용한 dfs과정으로 다시 문제를 해결하였습니다. 

코드는 아래와 같습니다.

import sys

preorder = []

while(1):
    string_ = sys.stdin.readline().rstrip()
    if string_ == '':
        break
    preorder.append(int(string_))

inorder = preorder[:]
inorder.sort()

stack = []
# build initial stack
root = preorder[0]
idx = inorder.index(root)
stack.append([preorder[1:1+idx], inorder[:idx]])
stack.append([preorder[1+idx:], inorder[idx+1:]])
stack.append([[root], [root]])

ans = []
while(stack):
    preorder_, inorder_ = stack.pop()

    if len(preorder_) == 1:
        ans.append(preorder_[0])
        continue
    if len(preorder_) == 0:
        continue
    root = preorder_[0]
    idx = inorder_.index(root)
    stack.append([preorder_[1:1+idx], inorder_[:idx]])
    stack.append([preorder_[1+idx:], inorder_[idx+1:]])
    stack.append([[root], [root]])

for e in ans[::-1]:
    print(e)