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

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

Minimum Distance Between BST Nodes - LeetCode

 

 1. 재귀 구조로 중위 순회

 BST의 왼쪽 자식은 항상 루트보다 작고, 오른쪽 자식은 항상 루트보다 크다.

 그렇다면 루트 D와 가장 차이가 작을 수 있는 노드는 딱 2개 노드만 가능한데 바로 I와 G이다.

 파란 글씨의 순서대로 탐색하면서 거리를 계산해 나가면 값의 차이가 가장 작은 노드의 값을 찾을 수 있다.

# Definition for a binary tree node.
# 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: Optional[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