[리트코드] 530. Minimum Absolute Difference in BST

문제

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

Constraints:

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

---

✔ 문제접근 #1 중위순회[통과] ⭕

Intuition

이진 탐색트리의 특징을 이용하면 탐색트리를 배열로 나타냈을 때 왼쪽부터 크기의 오름차순으로 정렬되게 된다.

그러므로 배열로 나타내기 위해 트리의 중위순회하여 현재 값과 이전값의 크기를 비교하여 최소가 되는 노드사이 거리를 구한다.

Algorithm

재귀 방식으로 중위순회한다. pre 변수를 통하여 방문했던 노드 이전의 값을 기록하여 현재 노드값과 비교할 수 있도록한다. 비교할 때마다 노드 크기차이의 최솟값을 갱신해 나간다.

# 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:
    pre = None;
    ans = sys.maxsize
    
    def inorder(self, node):

        if node.left != None:
            self.inorder(node.left)
        
        if self.pre == None:
            self.pre = node.val
        else:
            self.ans = min(self.ans, abs(self.pre - node.val))
            self.pre = node.val
        
        if node.right != None:
            self.inorder(node.right)
        
    
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:

        self.inorder(root)
        
        return self.ans

 

Complexity Analysis

• 시간 복잡도 : O(N)
  • 모든 노드 탐색 O(N)
  • 그러므로 전체시작복잡도 : O(N)
• 공간복잡도 : O(1)

---

기타풀이 및 회고

해당 문제는 이진탐색트리의 특징을 알고있어야 풀 수 있는 문제이다. 순회하는 방식에 따른 탐색순서를 잘 관찰해야한다. 이진탐색트리와 연관된 기출문제를 많이 본 것 같다. 중요!