LeetCode Top Interview 150) Minimum Absolute Difference in BST

Question

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

Constraints:

• The number of nodes in the tree is in the range [2, 104].
• 0 <= Node.val <= 10^5

# 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:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:

---

---

보기 코드의 TreeNode구조를 가진 이진 트리의 루트 노드 root가 주어집니다. 트리의 전체 노드 중 두 노드의 차의 최솟값을 구하는 문제입니다. 이웃한 두 노드나 두 자식노드 사이가 아니라는 점에 유의해야 합니다.

제가 생각한 코드는 다음과 같습니다.

from heapq import heappop, heapify
# 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:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        stack = [root]
        val_list = []

        while stack:
            node = stack.pop()
            val_list.append(node.val)
            if node.left:
                stack.append(node.left)
            if node.right:
                stack.append(node.right)
        return self.getAnswer(val_list)

    def getAnswer(self,val_list: list) -> int:
        heapify(val_list)
        answer = 10**5
        last_val = heappop(val_list)

        while val_list:
            val = heappop(val_list)
            answer = min(answer,abs(last_val-val))
            last_val = val

        return answer

• stack : 노드를 순회하기 위해 노드를 저장하는 리스트입니다.
• val_list : 전체 노드의 값들을 저장하는 리스트입니다.
• 전체 노드를 순회하며 값들을 저장합니다. 어차피 전체를 순회한다는 것 외에 조건이 없으므로 깊이,너비 무엇을 우선으로하든 상관이 없습니다.
• 전체 값이 저장된 리스트 val_list를 getAnswer함수에 입력합니다.
  -getAnswer(list) : 리스트를 힙 구조화하여 작은값부터 탐색합니다. 탐색해가면서 두 값의 차가 최소인 값을 answer에 저장합니다.

---

몇 가지 포인트를 짚어보면서 풀었습니다.
우선 전체 노드의 값을 알아야 한다는 점에서 전체 탐색을 하는 코드를 작성했습니다.

그리고나서 전체 값들 중 차이가 최소인 값을 찾기 위해서는 리스트의 전체 값끼리 비교해봐야 했고 차라리 정렬해서 이웃한 값끼리 비교하는 편이 가독성이 더 좋고 시간복잡도 면에서도 과하지 않을거라는 생각이 들었습니다.

전체 노드 중 두 값을 확인해봐야 하는건 결국 O(n)만으로는 불가능하다 생각해서 정렬쪽으로(O(nlogn)) 생각을 하게 되었습니다.

======================================================
다른 사람과의 풀이를 비교하는 도중 그냥 트리구조가 아니라 BST라는걸 뒤늦게 확인했네요...이런..

그러던 와중 굉장히 신박한 코드를 발견해서 살펴보겠습니다.

# 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(object):
    def getMinimumDifference(self, root):
        def fn(node, lo, hi):
            if not node: return hi - lo
            left = fn(node.left, lo, node.val)
            right = fn(node.right, node.val, hi)
            return min(left, right)
        return fn(root, float('-inf'), float('inf'))

• BST구조의 특징을 이용하여 재귀함수를 통해 깊이탐색을 하는 코드입니다.
• 깊이탐색 재귀함수 fn(node,lo,hi)를 반환하는 구조입니다.
• fn함수는 현재의 노드 node, 현재 노드까지의 최솟값 lo와 최댓값 hi을 가집니다.
  • left 왼쪽 서브트리에서의 최솟값, 최댓값의 차이입니다.
  • right 오른쪽 서브트리에서의 최솟값, 최댓값의 차이입니다.
  • 반환값은 left와 right 중 최솟값입니다.

즉, 가장 깊은 노드부터 올라오면서 최대, 최소의 차이가 작은 값을 반환하면서 올라오는 구조입니다.

노드를 한번만 방문하므로 시간복잡도는 O(n)을 가지고 공간복잡도 또한 최악으로해도 O(n)입니다. BST의 구조를 효율적으로 활용한 탐색방법입니다.