[BOJ][Python] 백준 2263 번: 트리의 순회

1일 1PS 92일차!

📚 문제

---

[골드 1] - 트리의 순회

💡 풀이 과정

---

• 우선 트리의 순회에 대해서 살펴보아야한다.

• 중위 순회, Inorder
  • left -> root -> right 순서대로 순회한다.
  • 위 트리에서는 (1) -> (3) -> (4) -> (5) -> (6) -> (7) -> (12) -> (15) -> (16) 순서로 순회한다.

• 전위 순회, Preorder
  • root -> left -> right 순서대로 순회한다.
  • 위 트리에서는 (7) -> (3) -> (1) -> (5) -> (4) -> (6) -> (15) -> (12) -> (16) 순서로 순회한다.

• 후위 순회, Postorder
  • left -> right -> root 순서대로 순회한다.
  • 위 트리에서는 (1) -> (4) -> (6) -> (5) -> (3) -> (12) -> (16) -> (15) -> (7) 순서로 순회한다.

• 해당 문제에서는 중위 순회와 후위 순회가 주어진다.
  • 하나의 노드는 결국 Left Nodes, Root Node, Right Nodes 3가지로 나뉠 수 있으며 이들의 순서만 순회 방법에 따라 다르다.
  • 중위 순회 : Left Nodes, Root Node, Right Nodes
  • 후위 순회 : Left Nodes, Right Nodes, Root Node
  • 두 순회를 보고 Root Node 를 확정지을 수 있으며 이후 Left Nodes, Right Nodes 에 동일한 작업을 진행하면 된다. 즉, 재귀함수를 사용할 수 있다.
• 우선 재귀함수의 종료 조건을 먼저 작성한다. inOrder 존재 여부를 사용했다.
• 이후 root 는 주어진 postOrder 의 마지막 요소임이 확정이다.
• 또한 해당 요소의 inOrder 에서의 index 값을 통해 Left Nodes, Right Nodes 를 구분지을 수 있다.
• Left 와 Right 에 대해서 재귀함수를 진행하며 Right 에서는 root 의 위치에 주의한다.

• Print 와 left, right 처리 순서에 대해서도 후위 순회 조건에 맞게 배치한다.

• 처음에는 배열을 넘겼다가 메모리 초과로 인해 index 를 넘겼다.
  • 이때 index 로 넘긴다면 postOrder 의 index 넘김에 주의해야하는데, inOrder 를 통해 Left Nodes 의 개수를 파악해 설정해야 한다.

📌포인트

---

• TLE
  • 기존에는 rootInIdx = inOrder.index(root) 를 사용해 index 를 구했다.
  • 이는 O(n^2) 로 시간초과를 발생시켰다.
  • 이후 중위 순회의 인덱스만 기록하는 테이블을 생성해 시간복잡도를 낮췄다.

💻 코드

---

import sys
sys.setrecursionlimit(1000000)

n = int(input())
inOrder = list(map(int, input().split()))
postOrder = list(map(int, input().split()))

# 중위 순회의 값과 인덱스를 저장하는 해시 테이블
inOrder_index = {val: idx for idx, val in enumerate(inOrder)}

answer = ""

def preOrder(inOrder_start, inOrder_end, postOrder_start, postOrder_end):
    global answer

    if inOrder_start > inOrder_end or postOrder_start > postOrder_end:
        return

    root = postOrder[postOrder_end]
    answer += str(root) + " "

    rootInIdx = inOrder_index[root]

    preOrder(inOrder_start, rootInIdx - 1, postOrder_start, postOrder_start + (rootInIdx - inOrder_start) - 1)
    preOrder(rootInIdx + 1, inOrder_end, postOrder_start + (rootInIdx - inOrder_start), postOrder_end - 1)



preOrder(0, n - 1,0, n - 1)
print(answer)