🦊 트리의 순회

1. 문제 링크

16509번: 트리의 순회

2. 코드

import sys
sys.setrecursionlimit(10 ** 6)

def find_root(in_start, in_end, post_start, post_end):
    global in_order_index
    global post_order
    
    if in_start > in_end or post_start > post_end:
        return
    
    root = post_order[post_end]
    in_root_index = in_order_index[root]
    
    left_root = in_root_index - in_start
    right_root = in_end - in_root_index
    
    print(root, end = " ")
    find_root(in_start, left_root + in_start - 1, post_start, left_root + post_start - 1)
    find_root(in_end - right_root + 1, in_end, post_end - right_root, post_end - 1)
    

n = int(input())

in_order = list(map(int, input().split()))
post_order = list(map(int, input().split()))

in_order_index = [0] * (n + 1)
for i in range(n):
    in_order_index[in_order[i]] = i

find_root(0, n - 1, 0, n - 1)

Python3 71288kb 400ms

• 틀린 코드 (메모리 초과)

    def index_of(list, elem):
        for i in range(len(list)):
            if list[i] == elem:
                return i
        return -1
      
    ans = []
    def find_root(in_order_subtree, pre_root, start_index):
        global ans
        global post_order
      
        # print(in_order_subtree, pre_root, start_index)
        ans.append(pre_root)
        # 루트 인덱스를 기준으로 in order의 왼쪽 오른쪽 분리
        root_index = index_of(in_order_subtree, pre_root)
        if root_index < 0:
            return
          
        left_subtree = in_order_subtree[0 : root_index]
        right_subtree = in_order_subtree[(root_index + 1) : len(in_order_subtree)]
          
        # print(left_subtree, right_subtree)
          
        # post order 에서 왼쪽 서브트리와 오른쪽 서브트리 경계를 찾음
        left_root_index = start_index + len(left_subtree) - 1
        if left_subtree and left_root_index != -1:
            find_root(left_subtree, post_order[left_root_index], start_index)
      
        right_root_index = start_index + len(left_subtree) + len(right_subtree) - 1
        if right_subtree and right_root_index != -1:
            find_root(right_subtree, post_order[right_root_index], start_index + len(left_subtree))
      
    n = int(input())
      
    in_order = list(map(int, input().split()))
    post_order = list(map(int, input().split()))
      
    find_root(in_order, post_order[-1], 0)
    print(' '.join(str(i) for i in ans))
  

3. 해설

• 해설

    # 왼쪽 서브트리와 오른쪽 서브트리를 찾는 것을 반복하면서 트리를 분리함
      
    # 1. post order 의 가장 마지막 노드는 루트 노드
    # 2. in order 에서 루트 노드를 기준으로 왼쪽과 오른쪽 서브트리 찾음
      
    # 3. in order 에서 찾은 경계를 통해 post order 에서 왼쪽과 오른쪽 서브트리의 경계를 찾음
    # 4. 경계의 왼쪽에서 마지막 노드는 왼쪽 서브트리의 루트 노드임
    # 마찬가지로 오른쪽에서 마지막 노드는 오른쪽 서브트리의 루트 노드임
      
    # 5. pre order 에서는 루트가 먼저 나오기 때문에 루트를 찾을 때 마다 출력하면됨
    # 반복