[Leetcode] 530. Minimum Absolute Difference in BST (python)

#1.  문제

https://leetcode.com/problems/minimum-absolute-difference-in-bst/

Minimum Absolute Difference in BST - LeetCode

 

 

이진 탐색 트리가 주어질 때, 두 노드값들의 차이 중 가장 최솟값을 찾는 문제

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

Output: 
1

Explanation:
노드 1과 2의 차이가 1로 가장 작다.

 

---

#2.  풀이

 

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


class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        import sys

        def dfs(node, stack):

            # Base case
            if node is None:
                return

            # Stacking values
            stack.append(node.val)

            # Recursive
            dfs(node.left, stack)
            dfs(node.right, stack)

            # Return the stack at the end
            return stack

        stack = []

        stacked = dfs(root, stack)
        stacked.sort()

        min_val = sys.maxsize

        for i in range(1, len(stacked)):
            diff = abs(stacked[i] - stacked[i - 1])
            min_val = min(min_val, diff)
        return min_val

 

난이도 자체는 그렇게 어렵지 않지만, 수월한 이해를 도모하기 위해 최적화를 하지 않고 직관적으로 풀려고 노력했다.보통 재귀 과정에서 계산하는 로직으로 좀 더 세련된 코드를 작성할 수 있지만, 아직은 조금 어렵기 때문에단순히 stack에 탐색한 노드만 쌓아두고 이후 알고리즘을 전개하는 형태로 풀었다.

 

dfs를 통해 각 노드의 값을 스택에 쌓고, 다 쌓은 스택을 반환한다.이때 스택을 정렬하는 것이 중요한데, 이유는 모든 노드 값의 차이 중 가장 작은 값을 찾으면 되기 때문이다.즉, 정렬 상태에서는 바로 이전 값과의 차이는 이후의 값들과의 차이보다 항상 작기 때문이다.따라서 이전 값하고의 차이로 계속해서 최솟값을 갱신하면 된다.

 

가장 작은 최솟값을 찾는 문제가 아니라면 로직이 꽤나 복잡해질 수 있는 문제다.