[BOJ_2263] 트리의 순회

2263번: 트리의 순회

 

✅ 문제 설명

• BOJ_4256 문제와 비슷한 문제입니다. (https://wnszero.tistory.com/10)
• 이진 트리의 인오더(중위순회)와 포스트오더(후위순회)가 주어졌을 때, 프리오더를(전위순회) 구하는 문제입니다.

 

✅ 접근 방식

• 중위순회, 후위순회 2개의 결과를 종합하여 각각의 결과에서의 루트와 왼쪽서브트리, 오른쪽 서브트리를 알아내고, 이를 이용해서 (루트)(왼쪽 서브트리)(오른쪽 서브트리)순으로 탐방순서를 배치해 전위순회를 시행하면 원하는 결과를 얻을 수 있습니다.

 

✅ 코드 설명

def preorder(in_start, in_end, post_start, post_end):
    if in_start > in_end:
        return
    if post_start > post_end:
        return
    root = postorder[post_end]
    idx = inorder.index(root)  # 루트의 인덱스
    left_len = idx - in_start
    answer.append(root)  # 루트
    preorder(in_start, in_start + left_len - 1, post_start, post_start + left_len - 1)  # 왼쪽 서브트리
    preorder(in_start + left_len + 1, in_end, post_start + left_len, post_end - 1)  # 오른쪽 서브트리

• 전위순회 로직입니다.
• 인자 in_start, in_end: 중위순회 결과를 저장한 배열에 접근하기 위한 시작 인덱스, 끝 인덱스
• 인자 post_start, post_end: 후위순회 결과를 저장한 배열에 접근하기 위한 시작 인덱스, 끝 인덱스
• 이처럼 인덱스를 넘겨주는 이유는 서브트리에 해당하는 노드들의 리스트를 넘겨주는 대신에, 시작과 끝 인덱스를 넘겨주어 하나의 리스트를 재활용하기 위함입니다.

---

• 시작인덱스가 끝 인덱스를 넘어가면 안되므로, in_start>in_end이거나 post_start>post_end이면 종료합니다. (종료조건)
• 루트값은 후위순회의 젤 마지막 값이므로 postorder[post_end]를 통해 알 수 있습니다.
• 왼쪽 서브트리에 해당하는 노드의 개수를 구하기 위해, 루트의 인덱스를 idx = inorder.index(root)로 구한 뒤 중위순회의 시작인덱스를 빼주면 왼쪽서브트리의 개수를 알 수 있습니다.
  • 왜냐하면 중위순회는 루트가 나오기전까지는 왼쪽 서브트리이기 때문에 시작~루트가 나오기전까지의 개수를 세면 왼쪽 서브트리의 개수가 됩니다.
• 이제 루트값과 왼쪽 서브트리의 개수를 알았으므로, 이를 이용해서 (루트)(왼쪽서브트리)(오른쪽서브트리)순으로 트리를 탐방하는 전위순회를 구현해줍니다.
• 아래 코드를 보면 첫번째줄에 루트를 방문하고, 두번째줄에서 중위, 후위순회의 왼쪽서브트리의 인덱스값을 넘겨주고, 세번째줄에서는 중위,후위순회의 오른쪽 서브트리의 인덱스 값을 넘겨줌으로써 (루트)(왼쪽서브트리)(오른쪽서브트리) 순으로 방문합니다.

answer.append(root)  # 루트
preorder(in_start, in_start + left_len - 1, post_start, post_start + left_len - 1)  # 왼쪽 서브트리
preorder(in_start + left_len + 1, in_end, post_start + left_len, post_end - 1)  # 오른쪽 서브트리

 

 

---

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

answer = []
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))

preorder(0, n - 1, 0, n - 1)

print(*answer)

노드의 개수 n을 입력받고, 정답을 저장할 빈 배열 answer를 선언해두었습니다.

문제에서 주어지는 중위순회, 후위순회의 결과를 각각 inorder, postorder배열에 저장해두고, 우리는 전위순회를 결과값으로 내야하므로 preorder함수를 호출합니다. (이때 인자값에는 각각 inorder,postorder의 시작 인덱스, 끝 인덱스를 전달해줍니다.)

 

✅ 최종 코드

# 트리의 순회

import sys

sys.setrecursionlimit(10 ** 5)


def preorder(in_start, in_end, post_start, post_end):
    if in_start > in_end:
        return
    if post_start > post_end:
        return
    root = postorder[post_end]
    idx = inorder.index(root)  # 루트의 인덱스
    left_len = idx - in_start
    answer.append(root)  # 루트
    preorder(in_start, in_start + left_len - 1, post_start, post_start + left_len - 1)  # 왼쪽 서브트리
    preorder(in_start + left_len + 1, in_end, post_start + left_len, post_end - 1)  # 오른쪽 서브트리


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

answer = []
inorder = list(map(int, sys.stdin.readline().split()))
postorder = list(map(int, sys.stdin.readline().split()))

preorder(0, n - 1, 0, n - 1)

print(*answer)

 

❇️ 코멘트

• inorder.index(root)를 사용하여 루트의 인덱스를 찾도록 했습니다. 이렇게 하면 불필요한 반복문을 사용하지 않고도 루트의 위치를 찾을 수 있습니다. (메모리 초과 해결의 KEY✨)
• BOJ_4256에서는 for루프를 돌면서 left_len(=왼쪽 서브트리의 크기)를 찾았는데 여기서는 위와 같이 함으로써 메모리를 더 적게 사용할 수 있었습니다. (발전사항)

 

메모리 초과  해결 코드

(전)

    left_len = 0
    for i in range(in_start, in_end):
        if inorder[i] == root:
            break
        left_len += 1

(후)

    idx = inorder.index(root)  # 루트의 인덱스
    left_len = idx - in_start