Week 3-1. [Binary Search Tree (BST)] 530. Minimum Absolute Difference in BST (Python3)

문제 해결 과정

✍️ 문제 요약

https://leetcode.com/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150 

Minimum Absolute Difference in BST - LeetCode

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.

 

➡️ BST가 주어진다. 주어진 BST에 포함된 노드 중 서로 다른 두 노드의 차의 최솟값을 반환하라.

 

🔎 어떤 식으로 접근했는가?

문제에서 BST가 주어졌다. BST의 특징은, 부모 노드가 왼쪽 자식 노드보다 크고 오른쪽 자식 노드보다 작다는 것이다.

 

따라서 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:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        nums = list()
        self.inorder(root, nums) # root 노드부터 중위 순회
        # 모든 노드 중위순회 후에 nums에는 오름차순으로 원소가 저장되어 있다.
        mn = 1e9
        for i in range(len(nums)-1):
            mn = min(mn, nums[i+1]-nums[i])
        return mn

    # 중위 순회
    def inorder(self, node: TreeNode, lst: list) -> None:
        if node == None: return
        self.inorder(node.left, lst) # 왼쪽 자식 노드
        lst.append(node.val) # 나
        self.inorder(node.right, lst) # 오른쪽 자식 노드

 

위 코드의 시간 복잡도는 중위 순회를 통해 이진 트리의 모든 노드를 한 번씩 방문하므로 O(n)이다. 

문제에서 입력의 최대는 10^4이므로 감당할 수 있는 정도이다.

 

다른 사람의 코드를 탐구해보기

다른 사람의 코드도 중위순회하는 코드였고, 내가 본 코드 중에는 내 코드가 가장 깔끔했다.