[LeetCode 783] Minimum Distance Between BST Nodes

이진 탐색 트리(BST) 노드 간 최소 거리

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

Minimum Distance Between BST Nodes - LeetCode

 

 

Think

값들이 BST형태로 주어지고, 노드들 중 가장 작은 값 차이를 출력하는 문제

트리에서 현재 노드와 값 차이가 가장 적은 노드는 딱 두 개 중 하나이다.

두 개가 어느것인지는 그림으로 설명하는 게 이해가 쉬울 것 같다.

이런 트리가 있을 때, 노드 4와 가장 차이가 작은 후보 노드 2개는 각각 노드 4 의 왼쪽과 오른쪽 자식 트리 속에 하나씩 존재한다.

왼쪽 자식 트리에서 가장 오른쪽아래에 있는 노드, 즉 여기서는 노드 3

오른쪽 자식 트리에서 가장 왼쪽아래에 있는 노드, 즉 여기서는 노드 6이다.

BST이므로 왼쪽 자식 트리의 값들은 모두 현재 노드보다 작은 값을 갖는다. 그렇다면 그 중 현재 노드와 차이가 가장 작은 노드는 그 트리 내의 가장 큰 값이다.

같은 원리로 오른쪽 자식 트리도 그렇다.

그래서 모든 노드를 돌면서, 그 노드와 차이가 가장 작은 후보 노드 2개를 모두 비교해 전체 중 차이가 가장 작은 노드를 찾으면 된다.

반복이나 재귀로 풀 수 있다.

나는 재귀로 풀이로 풀어봤다.

중위 순회(왼쪽 자식 탐색-현재 노드 탐색-오른쪽 자식 탐색 순)를 하면서 이전에 구한 가장 작은 차이값과 이번에 구한 차이값을 비교해 더 작은 값만 가지고 다음 계산을 반복한다.

 

 

Solution

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

import sys

class Solution(object):
    
    # minDiffInBST 함수를 재귀호출 하며 값을 비교할 것이므로 함수 밖에 최소 차이값 변수 선언
    prev = -sys.maxsize #시스템상 가장 작은 값
    result = sys.maxsize #시스템상 가장 큰 값
    
    def minDiffInBST(self, root):
        """
        :type root: TreeNode
        :rtype: int
        """
        
        #재귀 구조 중위 순회(왼-root-오)
        #왼쪽 탐색
        if root.left : 
            self.minDiffInBST(root.left)
            
        #루트 노드 탐색
        self.result = min(self.result, root.val - self.prev) #이전 최소값 vs 현재 노드의 값과 직전 노드의 값의 차이(현재 차이값 계산한 것) 를 비교
        self.prev = root.val #현재 노드의 값을 prev에 저장해둠. 다음 루트노드 탐색에 사용
        
        #오른쪽 탐색
        if root.right :
            self.minDiffInBST(root.right)
            
        return self.result

 

 

 

Get