[알고리즘] Leetcode #783 이진 탐색 트리(BST) 노드 간 최소 거리 (Python)

---

↓↓↓ 아래는 내 리트코드 계정 ↓↓↓

leetcode.com/Jiwon_Lee/

Jiwon Lee - LeetCode Profile

 

---

문제 설명

Given the root of a Binary Search Tree (BST), return the minimum difference between the values of any two different nodes in the tree.

 

입출력 예

Example 1:

Input: root = [4,2,6,1,3] Output: 1

Example 2:

Input: root = [1,0,48,null,null,12,49] Output: 1

 

Constraints

• The number of nodes in the tree is in the range [2, 100].
• 0 <= Node.val <= 105

 

Code

import sys

class Solution:
    prev = -sys.maxsize # 클래스 멤버 변수 
    result = sys.maxsize
    
    # 재귀 구조 중위 순회 비교 결과
    def minDiffInBST(self, root):
        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

BST에서 두 노드 간 차이가 가장 작을 수 있는 선택지는 현재 노드보다 작은 값 중 가장 큰 값 (왼쪽 노드 중 가장 오른쪽 값)과 현재 노드보다 큰 값 중 가장 작은 값 (오른쪽 노드 중 가장 왼쪽 노드)이 될 수 있다. 이를 비교하기 위해 트리를 중위순회 (왼-루트-오)로 돌면서 재귀구조로 구현했다. 맨 처음 비교를 위해 prev, result라는 클래스 멤버 변수로 적절히 크고 작은 값을 설정해주고, 왼쪽 노드부터 차이를 계산해 작은 값을 저장하며 탐색한다. 이때, 최솟값은 여러 번 발생할 수 있지만, 결과적으로 가장 작은 값만 도출하면 되므로, self.result에 중복 저장하여 return 한다.