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

문제요약

이진탐색트리의 전위순회환 결과를 토대로 해당 트리를 후위순회한 결과를 출력하는 문제입니다.

나의 접근법

1) 전위순회를 통해 이진검색트리를 재현하기
2) 이진검색트리를 후위순회하여 그 순서를 출력하기

활용한 개념

1) 이진탐색트리

코드의 구현

이진탐색트리

    def add(self, data: int):
        """데이터 추가하기"""
        if self.root is None:
            self.root = Node(data)
            return

        current = self.root
        while True:
            if current.value < data:
                if current.right is None:
                    current.right = Node(data)
                    break
                current = current.right
            elif current.value > data:
                if current.left is None:
                    current.left = Node(data)
                    break
                current = current.left


    def postorder(self):
        """트리의 후위순회"""
        def post_order(node):

            if node is None:
                return
            post_order(node.left)
            post_order(node.righ

데이터의 추가

    def add(self, data: int):
        """데이터 추가하기"""
        if self.root is None:
            self.root = Node(data)
            return

        current = self.root
        while True:
            if current.value < data:
                if current.right is None:
                    current.right = Node(data)
                    break
                current = current.right
            elif current.value > data:
                if current.left is None:
                    current.left = Node(data)
                    break
                current = current.left

후위순회

    def postorder(self):
        """트리의 후위순회"""
        def post_order(node):

            if node is None:
                return
            post_order(node.left)
            post_order(node.right)
            print(node.value)

        post_order(self.root)

전체 코드

import sys
sys.setrecursionlimit(10**7)

nodes = [int(line.strip()) for line in sys.stdin.readlines()]


class Node:
    """노드 정의"""

    def __init__(self, value: int):
        self.value = value
        self.left = None
        self.right = None


class BSTree:
    """이진검색트리"""

    def __init__(self):
        """트리의 초기화"""
        self.root = None

    def add(self, data: int):
        """데이터 추가하기"""
        if self.root is None:
            self.root = Node(data)
            return

        current = self.root
        while True:
            if current.value < data:
                if current.right is None:
                    current.right = Node(data)
                    break
                current = current.right
            elif current.value > data:
                if current.left is None:
                    current.left = Node(data)
                    break
                current = current.left


    def postorder(self):
        """트리의 후위순회"""
        def post_order(node):

            if node is None:
                return
            post_order(node.left)
            post_order(node.right)
            print(node.value)

        post_order(self.root)

tree = BSTree()
for i in nodes:
    tree.add(i)

tree.postorder()

기억하자: 파이썬의 재귀한계

파이썬은 내부적으로 재귀함수를 호출할 수 있는 정도를 제한하고 있습니다.
Recursion Error 가 발생할 경우, 다음의 코드를 추가해줍니다.

import sys
sys.setrecursionlimit(10**7)