greentea31's Note

https://leetcode.com/problems/minimum-distance-between-bst-nodes/

풀이 과정

이진 탐색 트리의 임의의 두 노드의 차의 최소값을 구하는 문제이다.

이진 탐색 트리의 특성상 특정 노드의 왼쪽 서브트리에는 자신보다 작은 노드 값을 가진 노드들만이 존재하고, 오른쪽 서브트리에는 큰 노드 값을 가진 노드들만이 존재한다.

자신보다 작으면서 차이는 가장 적은 노드 값을 찾으려면 어느 노드에 방문해야 할까? 왼쪽 자식 노드로 한번 이동해서, (자신보다 작은 노드 값들 중에서) 가능한 오른쪽으로 쭉 이동하면, (그 중에서 가장 큰 노드 값으로 가면) 원하는 노드 값을 찾을 수 있다.

마찬가지로, 자신보다 크면서 차이는 가장 적은 노드 값을 찾으려면 오른쪽 자식 노드로 한번 이동 후. 가능한 왼쪽 자식 노드로 쭉 이동하면 원하는 노드 값을 찾을 수 있다.

트리의 3가지 순회 방법중, 왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리 순으로 방문하는 중위 순회를 이용해 순회하고, 현재 노드를 순회하기 전에 방문했던 노드 값을 저장하고 있는 변수를 두면 모든 노드에서 자신보다 작거나, 크면서 차이가 가장 적은 노드 값과 자신의 노드 값과의 차를 구할 수 있고, 그 중 가장 작은 값을 정답으로 반환해주면 된다.

[10, 5, 15, 3, 7, 11, 17]을 노드 값으로 가지고 있는 이진 탐색 트리의 예시 그림이다. 중위 순회의 방문 순서를 같이 표시하였는데, 특정 노드에서 왼쪽 -> 오른쪽 쭉.... 의 노드와 오른쪽 -> 왼쪽 쭉....의 노드 방문 순서가 1씩 나므로, 현재 노드 값 - 이전 방문 노드 값을 모든 노드에서 구해주면 임의의 두 노드의 차 중 가장 작은 값을 확인할 수 있다.

소스 코드

class Solution:
    answer = sys.maxsize
    prev = -sys.maxsize
    def minDiffInBST(self, root: Optional[TreeNode]) -> int:
        if root.left:
            self.minDiffInBST(root.left)
        self.answer = min(self.answer, root.val - self.prev)
        self.prev = root.val
        if root.right:
            self.minDiffInBST(root.right)
        return self.answer