[백준 2024/09/17] 5639번 이진 검색 트리

1. 문제

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

 

2. 접근 방법

pre order 결과를 가지고, post order의 결과를 도출해야 하는 문제였다.

 

pre order이기에, <루트> <왼쪽 노드> <오른쪽 노드> 순으로 출력될 것이었다.

따라서, 처음 주어진 노드의 키는 전체 binary tree의 root node를 나타낼 것이다.

따라서, 이를 기준으로 다음으로 주어진 노드를 왼쪽에 배치할 것인지, 오른쪽에 배치할 것인지 결정해 주었다.

 

def get_nodes():
    root_num = int(input())
    root_node = Node(root_num)

    while True:
        try:
            new_node = Node(int(input()))
            cur_node = root_node

            while True:
                if new_node.root < cur_node.root:
                    if cur_node.left is None:
                        cur_node.left = new_node
                        break
                    else:
                        cur_node = cur_node.left

                else:
                    if cur_node.right is None:
                        cur_node.right = new_node
                        break
                    else:
                        cur_node = cur_node.right
        except:
            return root_node

위 코드는 입력 처리하는 함수이다.

해당 예제는 몇 개의 노드가 입력으로 주어질 지 언급되어 있지 않기에, try-except 문으로 예외 처리를 해주어야 했다.

 

except로 예외를 받게 되면, root_node 값을 반환해 주었다.

 

def postorder(root_node):
    stack = []
    cur_node = root_node

    while root_node:
        if cur_node.left:
            stack.append(cur_node)
            cur_node = cur_node.left
            continue
        elif cur_node.right:
            stack.append(cur_node)
            cur_node = cur_node.right
            continue
        else:
            print(cur_node.root)
            if stack:
                last_visit = stack.pop()
                if last_visit.left == cur_node:
                    last_visit.left = None
                else:
                    last_visit.right = None
                cur_node = last_visit
            else:
                break

 

다음으로는, post order로 입력 받은 값들을 출력해 주어야 했다.

post order은 왼쪽 노드, 오른쪽 노드를 모두 출력한 후 root node를 출력해 주어야 하기에, 왼쪽 노드, 오른쪽 노드의 유무에 따라 cur_node를 이동시켜 주었다.

 

처음에는 postorder 함수를 재귀로 작성하여 반환해 주었다. 하지만, recursion error로 인해 통과하지 못하여, stack을 이용해 주었다.

stack으로 pop된 것을 last_visit이라는 변수에 넣어주고, 현재 노드의 위치가 왼쪽, 오른쪽 이냐에 따라 last_visit.left = None or last_visit.right = None 을 처리해 주었다.

 

하지만, 이보다도 잘 쓴 코드가 있으리라 생각이 들어 다른 코드를 공부해 보게 되었다.

또한, 위 코드는 전위 순회로 주어진 결과를 잘 이용하지 못하였다. 

 

https://ku-hug.tistory.com/132

[Python/파이썬] 백준 5639번: 이진 검색 트리

따랏, 위 블로그를 참고하여 전위 순회를 후위 순회로 효과적으로 전환하는 지에 대해서 생각해 보고, 이를 코드로 작성해 보기도 하였다.

 

3. 코드

class Node:
    def __init__(self, root):
        self.root = root
        self.left = None
        self.right = None


def get_nodes():
    root_num = int(input())
    root_node = Node(root_num)

    while True:
        try:
            new_node = Node(int(input()))
            cur_node = root_node

            while True:
                if new_node.root < cur_node.root:
                    if cur_node.left is None:
                        cur_node.left = new_node
                        break
                    else:
                        cur_node = cur_node.left

                else:
                    if cur_node.right is None:
                        cur_node.right = new_node
                        break
                    else:
                        cur_node = cur_node.right
        except:
            return root_node


def postorder(root_node):
    stack = []
    cur_node = root_node

    while root_node:
        if cur_node.left:
            stack.append(cur_node)
            cur_node = cur_node.left
            continue
        elif cur_node.right:
            stack.append(cur_node)
            cur_node = cur_node.right
            continue
        else:
            print(cur_node.root)
            if stack:
                last_visit = stack.pop()
                if last_visit.left == cur_node:
                    last_visit.left = None
                else:
                    last_visit.right = None
                cur_node = last_visit
            else:
                break


if __name__ == "__main__":
    root_node = get_nodes()
    postorder(root_node)

 

 

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
def get_pre():
    while True:
        try:
            pre.append(int(input()))

        except:
            break


def print_post(start, end):
    if start > end:
        return
    mid = end + 1 # 오른쪽 sub tree 가 없을 때를 대비한, 설정
    for i in range(start+1, end+1):
        if pre[start] < pre[i]:
            mid = i
            break

    print_post(start+1, mid-1)
    print_post(mid, end)
    print(pre[start])


if __name__ == "__main__":
    pre = []
    get_pre()
    print_post(0, len(pre) - 1)