[Leetcode] 리트코드 - 이진 탐색 트리(BST) 노드 간 최소 거리(minimum-distance-between-bst-nodes) 파이썬(python) 풀이

문제

두 노드 간 값의 차이가 가장 작은 노드의 값의 차이를 출력하라.

입력

root = [4, 2, 6, 1, 3, null, null]

출력

1

노드 3과 노드 4의 값의 차이는 1이다.

입력

root = [10, 4, 15, 1, 8, null, null]

출력

2

이 경우 노드 간 값의 차이가 가장 작은 노드는 8과 10이다. 1과 4는 거리의 차이가 3이고, 4와 8은 차이가 4이지만 8과 10의 차이는 2로 최솟값이다.

코드

재귀 구조로 중위 순회

import sys


class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    prev = -sys.maxsize
    result = sys.maxsize

    # 재귀 구조 중위 순회 비교 결과
    def minDiffInBST(self, root: TreeNode) -> int:
        if root.left:
            self.minDiffInBST(root.left)

        self.result = min(self.result, root.val - self.prev)
        self.prev = root.val

        if root.right:
            self.minDiffInBST(root.right)


        return self.result

반복 구조로 중위 순회

import sys

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


class Solution:
    def minDiffInBST(self, root: TreeNode) -> int:
        prev = -sys.maxsize
        result = sys.maxsize

        stack = []
        node = root

        # 반복 구조 중위 순회 비교 결과
        while stack or node:
            while node:
                stack.append(node)
                node = node.left

            node = stack.pop()

            result = min(result, node.val - prev)
            prev = node.val

            node = node.right


        return result

풀이

값의 차이가 가장 작은 노드를 찾으려면 어디와 어디 노드를 비교해야 하는지 생각해보자. BST의 왼쪽 자식은 항상 루트보다 작고, 오른쪽 자식은 항상 루트보다 크다. 그렇다면 먼저, 다음과 같은 BST가 있다고 가정해보자.

이 경우 루트 D와 가장 차이가 작을 수 있는 노드는 딱 2개 노드만 가능한데, I와 G이다. 이외에는 항상 이들 노드보다 값의 차이가 클 것이다. D → B의 차이는 D → C보다는 무조건 크다. 왼쪽으로 갈수록 값이 더 작아지기 때문이다. D → A, D → F도 마찬가지다. D → C보다 작아질 수 없다. 따라서 D → B부터는 제외하고, 그렇다면 D → E 하위 노드들에 가능성이 있는데, 이 중에서도 D → H는 D → E보다 무조건 크기 때문에 마찬가지로 배제한다. 오른쪽 자식은 더 큰 값을 지니기 때문에 이 경우 D → I가 가장 작은 값이 될 수 있다.

물론 항상 정답은 아닐 수도 있다. 왜냐면 D → G가 의외로 가장 작은 값이 될 수 있기 때문이다 따라서 여기서는 D → I와 D → G 중 작은 값을 택하면 정답이 된다. 이제 이렇게 비교할 수 있는 알고리즘을 찾아내면 된다.

이번에는 직접 값을 입력해 그림으로 나타내보자. 이 문제에서 예제의 입력값은 너무 단순하므로 밑의 그림과 같이 [8,4,12,2,6,null,null,1,3,5,7] 정도로 입력값을 좀 더 복잡하게 정해 트리를 나타내 보자.

이 그림에는 두 노드 간 값의 차이가 가장 작은 노드를 계산하기 위한 순서를 표시 했다. 이 순서대로 탐색하면서 각 거리를 계산해 나가면 값의 차이가 가장 작은 노드의 값을 찾을 수 있다. 여기서 루트인 8은 7과 12 두 군데를 비교해보는데, 앞서 설명한 D → I, D → G인 비교 대상과 동일함을 확인할 수 있다. 참고로 여기서 정답은 1이며 이렇게 값의 차이가 1인 노드가 여럿 있다. 그러나 최솟값을 출력하기만 하면 되므로, 중복된 값인 1을 정답으로 출력하면 된다.

이렇게 비교할 수 있는 탐색 순서는 중위 순회를 하면서 이전 탐색 값과 현재 값을 비교하면 바로 이 순서대로 비교할 수 있을 것 같다.

재귀 구조와 반복 구조에서 호출될 때마다 변수값은 다음과 같다.

출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]