파이썬(알고리즘) :: 이진 탐색 트리에서 최소합 찾기

이번에는 이진 탐색 트리 개념과 이진 탐색 트리에서 최소합을 찾는 문제에 대하여 정리해보려고 한다.

이진 탐색 트리는 이진탐색과 연결리스트의 장점을 합친 개념으로 그림으로 간단히 그리면 아래와 같다.

 

# 이진탐색트리 예시

 

이진 트리는 위 그림과 같은 형태로 표햔된다.

 

구조는 최상위 노드(위 그림에서는 8)를 기준으로 아래에 자식 노드가 존재 한다.

자식노드의 왼쪽은 노드 보다 작은 수, 오른쪽은 노드 보다 큰 수가 배치된다.

그리고 그 하위 노드들도 위와 같은 방법으로 중복 없이 정렬하면 트리가 완성된다.

 

이진트리는 중복 없이 최상위 노드를 기준으로 크기에 따라 정렬하기 때문에 효율적으로 탐색할 수 있다.

탐색 유형에는 총 3가지가 있으며 간단히 정의하면 아래와 같다.

 

1.  전위순회 : 부모 방문 -> 왼쪽 자식들 방문 -> 오른쪽 방문   ex) 1 2 4 5 3 6 7

2. 중위순회 : 왼쪽 방문 -> 부모 방문 -> 오른쪽 방문  ex) 4 2 5 1 6 3 7

3. 후위순회 : 왼쪽 방문 -> 오른쪽 방문 -> 부모 방문  ex) 4 5 2 6 7 3 1

 

이제 아래 문제를 살펴보자

 

# 예제 문제 

 

 

문제는 위 그림과 같은 이진 트리가 주어지고 합이 가장 적은 경로의 합을 문제이다,

위 그림과 같이 트리가 주어졌을때, 합이 가장 적은 경로는 8 -> 3 -> 1 이기 때문에 12가 리턴되어야 한다.

 

먼저 문제를 풀때 Node를 Class 로 선언 하여, 자식 노드를 순회할때 Class 내의 노드의 value, 그리고 왼쪽 자식 노드(left) 오른쪽 자식노드(right)를 사용한다.

 

# 정답 코드

class Node:
    def __init__(self, value, left=None, right=None):
    ''' 노드 설정 '''
        self.value = value
        self.left  = left
        self.right = right
      
    def size(self):
    '''
    트리 사이즈 계산
    최상위 root 노드를 기준으로 왼쪽 노드의 개수 + 오른쪽 노드의 개수 + 1 return
    '''
        l = self.left.size() if self.left else 0
        r = self.right.size() if self.right else 0
        return l + r + 1
        
    def __str__(self):
    ''' 호출 시 return과 같은 문자열 출력'''
        return f'<Node: value={self.value}, left={self.left}, right={self.right}>'


def min_path_sum(root):
''' 최소 값 찾는 func '''
    m = float('inf')
    q = [(root, root.value)]

    while q:
        node, curr_sum = q.pop()

        if not node.left and not node.right:
            if m > curr_sum:
                m = curr_sum
            continue

        if node.left:
            q.append((node.left, curr_sum + node.left.value))
        if node.right:
            q.append((node.right, curr_sum + node.right.value))

    return m
    
node = Node(10, Node(5, None, Node(2)), Node(5, None, Node(1)))
print(min_path_sum(node))

 

# 실행결과

(base) Waveui-MacBookPro:coding_test wave$ python bs1.py 
15