[백준][재귀] 트리의 순회

BAEKJOON Online Judge(BOJ) 문제입니다.

https://www.acmicpc.net/

Baekjoon Online Judge

 

문제

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

2263번: 트리의 순회

 

내가 작성한 코드

import sys

sys.setrecursionlimit(10 ** 8)

def read_data():
    n = int(input())
    inorder = list(map(int, input().rstrip().split()))
    postorder = list(map(int, input().rstrip().split()))

    return n, inorder, postorder

def recursion(inorder, postorder, position, il, ir, pl, pr):
    if pl > pr:
        return

    # root
    root = postorder[pr]
    print(root, end=' ')

    offset = ir - position[root]

    #left
    recursion(inorder, postorder, position, il, ir-offset-1, pl, pr-offset-1)

    # right
    recursion(inorder, postorder, position, ir - offset + 1, ir, pr - offset, pr-1)

n, inorder, postorder = read_data()
position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i
recursion(inorder, postorder, position, 0, n-1, 0, n-1)
print()

• 중위순회와 후위순회
  
  • 후위순회의 마지막 탐색이 루트(root)
  • 중위순회에서 root의 인덱스 찾기(index)
  • 처음 ~ index-1 재귀 -> left
  • index ~ 마지막 재귀 -> right

 

다른 사람이 작성한 코드

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

# 분할 정복 방식으로 전위 순회를 찾음
def preorder(in_start, in_end, post_start, post_end):
    # 재귀 종료 조건 (수렴)
    if(in_start > in_end) or (post_start > post_end):
        return

    # 후위 순회 결과의 끝이 (서브)트리의 루트임을 이용
    parents = postorder[post_end]
    print(parents, end=" ")

    # 중위 순회에서 루트의 좌 우로 자식들이 갈라지는 것을 이용하여 left, right를 선언
    left = position[parents] - in_start
    right = in_end - position[parents]

    # left, right로 나눠 분할 정복 방식으로 트리를 추적하여 전위 순회를 찾아냄
    preorder(in_start, in_start+left-1, post_start, post_start+left-1) # 쪽 서브트리
    preorder(in_end-right+1, in_end, post_end-right, post_end-1) # 오른쪽 서브트리

n = int(input())
inorder = list(map(int, input().split()))
postorder = list(map(int, input().split()))

# 후위 순회의 끝값이 중위 순회의 어디 인덱스에 위치한지 확인을 위해
# 중위 순회의 값들의 인덱스값을 저장
position = [0]*(n+1)
for i in range(n):
    position[inorder[i]] = i

# 중위 순회, 후위 순회 모두 0부터 n-1 (전체 범위)값을 주고 전위 순회를 구함
preorder(0, n-1, 0, n-1)

• position
  
  • 중위 순회의 값으로 인덱스 해싱

https://velog.io/@bae_mung/Python-BOJ-2263-%ED%8A%B8%EB%A6%AC%EC%9D%98-%EC%88%9C%ED%9A%8C

[Python] BOJ 2263 : 트리의 순회

 

기억해야할 것

• 값으로 인덱스 찾기
  
  • 시간초과와 메모리 초과가 반복됨
  • 위 블로그에서 중위 순회값에 대한 후위 순회의 인덱스(position)을 통해 시간초과 극복