이진검색트리 (트리)

문제

이진 검색 트리는 다음과 같은 세 가지 조건을 만족하는 이진 트리이다.

  - 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다.

  - 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다.

  - 왼쪽, 오른쪽 서브트리도 이진 검색 트리이다.

전위 순회 (루트-왼쪽-오른쪽)은 루트를 방문하고, 왼쪽 서브트리, 오른쪽 서브 트리를 순서대로 방문하면서 노드의 키를 출력한다. 

후위 순회 (왼쪽-오른쪽-루트)는 왼쪽 서브트리, 오른쪽 서브트리, 루트 노드 순서대로 키를 출력한다. 예를 들어, 위의 이진 검색 트리의 전위 순회 결과는 50 30 24 5 28 45 98 52 60 이고, 후위 순회 결과는 5 28 24 45 30 60 52 98 50 이다.

이진 검색 트리를 전위 순회한 결과가 주어졌을 때, 이 트리를 후위 순회한 결과를 구하는 프로그램을 작성하시오.

 

입력

트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다.

 

출력

입력으로 주어진 이진 검색 트리를 후위 순회한 결과를 한 줄에 하나씩 출력한다.

 

예제 입력1

50
30
24
5
28
45
98
52
60

 

예제 출력1

5
28
24
45
30
60
52
98
50

 

- 문제 해결

이 방식으로 풀었었다. 리스트를 두개로 나눠서 사용해서 각자 하나씩 비교해서 값을 집어넣어 리스트의 개수를 낮추는 방식으로 문제를 풀었는데, 이 방식이 평균적으론 O(Nlog(N))으로 나오지만, 최악의 경우 즉 루트에서 왼쪽노드에만 존재하는 경우 또는 오른쪽노드에만 존재하는 경우에는 O(N^2)이라는 안좋은 결과가 나온다는 것을 파악했다.

import sys

sys.setrecursionlimit(10**6)  # 이것 처리 해줘야 재귀 1000 제한을 넘을 수 있음

# 입력 다 입력하고 Ctrl + Z + Enter
node_frt = []
for line in sys.stdin:
    node_frt.append(int(line))

result = []


def dfs(root, left, right):
    if len(left) == 0 and len(right) == 0:
        result.append(root)
        return

    if len(left) != 0:
        tmp_root = left[0]
        tmp_left = []
        tmp_right = []
        for idx, l in enumerate(left):
            if idx == 0:
                continue
            if tmp_root > l:
                tmp_left.append(l)
            else:
                tmp_right.append(l)
        dfs(tmp_root, tmp_left, tmp_right)

    if len(right) != 0:
        tmp_root = right[0]
        tmp_left = []
        tmp_right = []
        for idx, r in enumerate(right):
            if idx == 0:
                continue
            if tmp_root > r:
                tmp_left.append(r)
            else:
                tmp_right.append(r)
        dfs(tmp_root, tmp_left, tmp_right)

    result.append(root)


if len(node_frt) != 0:

    start_root = node_frt[0]
    left = []
    right = []
    for n in node_frt:
        if n == start_root:
            continue
        else:
            if start_root < n:
                right.append(n)
            else:
                left.append(n)

    dfs(start_root, left, right)

for i in result:
    print(i)

그래서 이 방식이 되게 안좋은 방식이라는 생각이 들어 정석풀이를 찾아보게 되었다.

전혀 이 방식을 생각하지도 못했다. 대단한 것 같다..

import sys

sys.setrecursionlimit(10**6)  # 이것 처리 해줘야 재귀 1000 제한을 넘을 수 있음
input = sys.stdin.readline

preorder = []
for line in sys.stdin:
    preorder.append(int(line.strip()))

idx = 0
n = len(preorder)
result = []


def build(lower, upper):
    global idx

    if idx >= n:
        return

    cur = preorder[idx]

    # 현재 값이 이 서브트리에 들어올 수 없는 값이면 종료
    if not (lower < cur < upper):
        return

    # 현재 값을 루트로 사용
    idx += 1

    # 왼쪽 서브트리
    build(lower, cur)

    # 오른쪽 서브트리
    build(cur, upper)

    # 후위 순회이므로 마지막에 루트 추가
    result.append(cur)


build(float("-inf"), float("inf"))

print("\n".join(map(str, result)))