[백준 5639번][Python] - 이진 검색 트리

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

 

 

# 풀이과정

전위 순회는 루트, 왼쪽, 오른쪽의 순서대로 노드를 방문한다. 그렇기에 맨 처음 주어지는 노드는 루트이고, 그 이후에는 하위 노드들이라고 볼 수 있다.

또한, 이진 트리이기에 한 노드의 왼쪽 서브트리의 모든 노드들은 해당 노드보다 작고, 오른쪽 서브트리의 모든 노드들은 해당 노드보다 크다는 사실을 인지해야한다.

 

그렇다면 차례대로 주어지는 노드들이 어떤 위치에 속해야 하는지는 어떻게 판단해야 할까?

이때 우리는 여러가지 경우의 수를 생각해 보아야한다.

• 우선, 부모로 예측되는 노드보다 크기가 작은 노드가 주어진다면, 해당 노드는 부모의 왼쪽 자식 노드이다.
• 반대로, 부모보다 크기가 큰 노드가 주어진다면, 해당 노드는 부모로 예측되는 노드의 오른쪽 자식이라고 바로 결정할 수 있을까? → 그렇지 않다. 부모의 부모를 조부모라고 하겠다. 만약 주어진 노드가 만약 조부모보다 크면 어떻게 할 것인가? → 그렇다면 조부모가 부모노드가 된다.

 

이를 정리하면 다음과 같다.

1. 맨 처음엔 루트 노드A가 부모이다.
2. 부모보다 작은 노드 B가 들어오면 해당 노드를 부모의 왼쪽 자식으로 삼고, B를 새로운 부모로 등록한다.
3. 만약 부모보다 큰 노드 C가 들어오면 해당 노드를 조부모와도 비교한다. 부모보다는 크고 조부모보다는 작다면, 해당 노드는 부모의 오른쪽 자식이다.
4. 하지만 조부모보다도 크다면, 조부모를 부모로 갱신하고, 조부모의 부모와도 비교를 한다.
5. 오른쪽 자식으로 등록이 되었다면, 해당 노드를 부모로 갱신한다.
6. 명심하자. 판단 과정에서 확실한 부모라고 판단되기 전까지는 예측상 부모일 뿐이다.

[코드 - 성공]

# ex_5639
import sys
sys.setrecursionlimit(100000)

tree = dict()
parent = 1e6
q = [parent]
nums = []
tree[parent] = [0,0]

# 노드 번호 입력받기
while True:
    try:
        nums.append(int(input()))
    except:
        break

# 기존 트리 복원
for node in nums:
    tree[node] = [0,0]
    # 판단 과정
    while True:
        if node < parent:
            q.append(node)
            tree[parent][0] = node
            parent = node    # 부모 업데이트
            break
        elif node < q[-1] and node > parent:
            tree[parent][1] = node
            q.append(node)
            parent = node
            break
        else:
            parent = q.pop()

# 후위 순회 출력
def sol(n):
    if n != 0:
        sol(tree[n][0])
        sol(tree[n][1])
        print(n)

root = tree[1e6][0]
sol(root)