BaekJoon 5639번 : 이진 검색 트리 (python)

BaekJoon 5639번 : 이진 검색 트리 (G4 37.780%)

이진 검색 트리 문제

전위 순회의 특징과 이진 검색 트리의 특징을 이용하여 후위 순회를 찾아낼 수 있는 문제이다.

• 전위 순회는 (루트)(왼쪽)(오른쪽)으로 진행하고 후위 순회는(왼쪽)(오른쪽)(루트)순으로 진행하게 된다.그리고 이진 검색 트리는 기본적으로 루트의 왼쪽은 루트보다 작게 되고 루트의 오른쪽은 루트보다 큰 숫자로 정렬되게 된다. 이 두 가지 특징을 조합하면 규칙성을 찾을 수 있게 된다.
• 전위 순회의 첫번째 원소부터 시작하여 해당 전위 순회 리스트에서 첫번째 원소보다 큰 원소를 찾아준다. 해당 원소는 오른쪽 서브트리의 시작점을 의미하게 되고 그 이전의 리스트 들은 왼쪽 서브트리라는 것을 알 수 있게 된다.
• 해당 원소의 index를 이용해서 왼쪽 서브트리와 오른쪽 서브트리로 분리하여 후위순회를 재귀적으로 돌아준다. 그렇게 왼쪽 서브트리출력 -> 오른쪽 서브트리 출력 -> 루트 출력순으로 재귀를 반복해주면 답을 도출할 수 있게 된다.
• 이 반복문에서 초반에 root = end + 1이라고 초기화 하는 이유는 만약 현재 리스트에서 루트 노드보다 큰 원소가 없을 경우 반복문에서 root값을 찾지 못하게 되고 이 때는 오른쪽 자식 노드가 없다는 것을 의미하기 때문에 이 상황을 표현하기 위한 초기화이다.

• 아예 다른 방법으로 두 특징을 이용하지 않고 이진 검색 트리라는 것만으로 이진 검색 트리 구조를 만들어 이 문제를 풀 수도 있게 된다.

Chat GPT (root변수를 반복문에서 end +1로 초기화 하는 이유?)

오른쪽 자식 노드의 시작 지점 설정: root 변수는 현재 노드(현재 서브트리의 루트 노드) 다음에 오는 첫 번째 오른쪽 자식 노드의 인덱스를 나타냅니다. root = end + 1로 설정하는 것은 기본적으로 오른쪽 자식 노드가 없다고 가정하는 초기 설정입니다. 즉, 현재 노드의 모든 후속 노드가 왼쪽 자식 (현재 노드보다 작은 값)만을 포함한다고 가정하는 것입니다.
조건에 따른 업데이트: 반복문에서는 num[start]보다 큰 첫 번째 값을 찾습니다. 이 값이 오른쪽 자식 서브트리의 시작점이 됩니다. 만약 이런 값이 발견되면 root를 해당 인덱스로 업데이트합니다. 그렇지 않다면 root는 초기값 end + 1을 유지하여 오른쪽 자식이 없음을 나타냅니다.
재귀 호출 조건: Postorder(start+1, root-1) 호출은 왼쪽 서브트리에 대한 후위 순회를 수행하고, Postorder(root, end) 호출은 오른쪽 서브트리에 대해 수행합니다. 만약 root가 end + 1을 그대로 유지한다면, Postorder(root, end)는 실제로 호출되지 않습니다(즉, 오른쪽 자식이 없습니다).

---

전위의 특징을 이용한 후위 순해 알아내기

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

num = list()
while True :
    n = input().strip()
    if n == '' :
        break
    num.append(int(n))

result = list()
def Postorder(start, end) :
    if start > end :
        return
    root = end + 1

    for i in range(start+1, end+1) :
        if num[i] > num[start] :
            root = i
            break
    Postorder(start+1, root-1)
    Postorder(root, end)
    print(num[start])

Postorder(0, len(num)-1)

---

이진 검색 트리 직접 구현

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**5)

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

class BinaryTree :
    def __init__(self) :
        self.root = None
    def _add(self, key) :
        if self.root is None :
            self.root = Node(key)
        else :
            self.add(self.root,key)
    def add(self, root, key) :
        if key < root.val :
            if root.left is None :
                root.left = Node(key)
            else :
                self.add(root.left, key)
        else :
            if root.right is None :
                root.right = Node(key)
            else :
                self.add(root.right, key)
    def Postorder(self, root) :
        if root :
            self.Postorder(root.left)
            self.Postorder(root.right)
            print(root.val)

BT = BinaryTree()
while True :
    n = (input().strip())
    if n == '':
        break
    BT._add(int(n))
    
BT.Postorder(BT.root)

---