[530. Minimum Absolute Difference in BST] (알고리즘)

September 6, 2023 6 분 소요

BST

문제

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.

Example 1:

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

Example 2:

Input: root = [1,0,48,null,null,12,49] Output: 1

Constraints:

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

Note: This question is the same as 783: https://leetcode.com/problems/minimum-distance-between-bst-nodes/

스스로 고민

접근법

BST가 뭔지는 알겠는데 막상 구현해서 문제를 풀려고 하니까 어떻게 해야될지 감이 안 잡혔다.
- (솔직히 문제가 무슨 소리인지도 이해가 가지 않았다)
우선 문제 자체가 이해가 가지 않으니 문제가 무슨 뜻인지 찾아봤다.
- 두 개의 서로 다른 노드 값 간의 절대 차이가 가장 작은 경우를 찾는 문제다
- 이게 무슨 소리냐면 BST는 각 노드가 최대 두 개의 자식 노드를 갖는다. 이 때 왼쪽 자식 노드는 현재 노드보다 작은 값을 가지고 오른쪽 자식 노드는 현재 노드보다 큰 값을 가진다. 따라서 BST에서 중위 순회를 수행하면 노드 값이 오름차순으로 정렬된 순서로 나오게 된다.
  - 수업시간에 중위 순회에 대해서 설명을 들었는데 설명을 잘해주셔서 그 때는 이해가 되었지만 막상 다시 문제를 접하니 무슨 소리인지 이해가 확실하게 가지 않았다. 그래서 좀 더 찾아봤다.

중위 순회가 뭘까?

중위 순회(In-order traversal)는 이진 트리(Binary Tree)에서 트리의 모든 노드를 왼쪽 서브트리를 먼저 방문한 후 현재 노드를 방문하고, 마지막으로 오른쪽 서브트리를 방문하는 순서로 트리를 탐색하는 알고리즘이다.

중위 순회는 주로 이진 검색 트리(Binary Search Tree, BST)와 같은 트리 자료 구조에서 사용된다. 중위 순회를 수행하면 BST의 노드들이 키(key) 값의 오름차순으로 순서대로 방문되기 때문에 정렬된 데이터를 얻을 수 있다.

중위 순회의 순서는 다음과 같다:

왼쪽 서브트리를 방문한다.
현재 노드를 방문한다.
오른쪽 서브트리를 방문한다.

솔직히 지금도 100% 이해가 안되지만 무슨 느낌인지는 알겠으니 문제를 풀면서 확실히 이해가면 아래에 정리를 다시 해놓기로…했지만 역시 이해가 안가서 그냥 무지성으로 해봤다.

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

위와 같이 노드에 값을 넣으면 아래와 같은 그림이 된다고 생각한다.

BST의 중위 순회를 하면 왼쪽 서브트리를 먼저 탐색하고 현재 노드 방문 그리고 오른쪽 서브트리를 탐색하는 순서라고 했다.

위의 BST를 중위 순회하면 1,2,3,4,6 과 같은 순서로 노드 값이 반환된다고 하는데 왜 그렇게 되는지 솔직히 이해가 안갔다. 😑

저번 과제에서 Hash Table 구현 문제가 있었는데 생각만하다가 시간을 다 써먹고 알고리즘 문제도 제대로 못 풀고 팀과제도 제대로 하지 못했다….

이번에 BST 문제가 두 개가 과제로 주어지기도 했고 도저히 어떤 식으로 풀어야할지 모르겠어서 지금 문제만 답을 보고 코드를 뜯어서 이해해야겠다고 생각했다. (다음 문제는 못 풀면 못 풀었지 풀 때까지 답을 보지 않을 생각…)

구현 코드

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):
        def inorder_traversal(node):
            if node is None:
                return []
            return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right)
        
        values = inorder_traversal(root)
        min_diff = float('inf')
        
        for i in range(1, len(values)):
            min_diff = min(min_diff, values[i] - values[i - 1])
        
        return min_diff
    
# BST를 만들기 위해 TreeNode 객체를 사용하여 트리 생성
root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

다른 사람들이 써 놓은 답중에 그나마 이해가 갈 수 있는걸 가져왔는데 솔직히 이 코드도 잘 이해가 가지 않았다. 그래도 하나하나 뜯어보자

if node is None:: 이 부분은 현재 노드 node가 None인 경우를 체크한다. BST에서 노드가 None인 경우는 해당 노드가 존재하지 않는 경우다. BST의 끝 부분(리프 노드)에 도달하면 None을 반환한다.
return []: 현재 노드 node가 None일 때, 즉 더 이상 노드가 없을 때 빈 리스트 []를 반환한다. 이렇게 하지 않으면 계속 호출된다. 따라서 빈 리스트를 반환함으로서 재귀 호출을 끝낸다, 리프 노드에서 끝나는 부분을 처리하기 위해 []를 반환한다.
return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right): 이 부분은 현재 노드 node가 None이 아닌 경우에 수행된다. 즉, 노드가 존재할 때 현재 노드의 값(node.val)과 왼쪽 서브트리(node.left)와 오른쪽 서브트리(node.right)를 중위 순회하고 그 결과를 리스트로 합친다.

깨달은 점!

멘토님이 BST는 재귀라고 했는데 답을 보면서 왜 재귀 안경 비유를 하셨는지 알게 되었다 ! 🥳
우선 values는 inorder_traversal 함수에 root 값을 넣는다. 이 때 root 는 위에서 넣은 TreeNode 값들이다.

root = TreeNode(4)
root.left = TreeNode(2)
root.right = TreeNode(6)
root.left.left = TreeNode(1)
root.left.right = TreeNode(3)

여기서 처음에 4가 들어있으니 지금 값은 none이 아니라서 return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) 여기로 넘어가진다.
이렇게 넘어가진 리턴 값에서 다시 inorder_traversal 함수가 호출되고 node.left 값이 들어간다. 여기에서 값은 2다.
node.left.val 값은 2인데 이 값도 null 이 아니니 return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) 가 다시 호출된다.
inorder_traversal(node.left) 가 다시 호출되고 여기서 node.left 값은 1이다.
여기서도 none이 아니니 또 다시 호출 inorder_traversal 함수 호출!
inorder_traversal(node.left) 값은 0이다 왜냐하면 1 의 왼쪽 아래에 아무것도 없기 떄문이다 그래서 이번에는 return [] 가 실행되면서 return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) 가 [] + [node.val] + inorder_traversal(node.right) 로 바뀌고 현재 값은 1이니깐 [] + [1] + [] 그리고 오른쪽 아래에 아무것도 없으니 왼쪽처럼 [] 를 반환한다.
그럼 지금 함수가 끝났으니 다시 상위로 올라가서 return inorder_traversal(node.left) + [node.val] + inorder_traversal(node.right) 의 값은 [1] + [2] + inorder_traversal(node.right) 이렇게 된다. inorder_traversal(node.right) 도 같은 논리로 진행되고 2의 오른쪽은 3이니 [1]+[2]+[3] 이된다. 이 함수가 호출이 끝났으니 이전에 호출된 4로 올라가고 여기서 오른쪽 6이므로 최종적으로 values 값은 [1,2,3,4,6] 이 된다.

	values = inorder_traversal(root)
	min_diff = float('inf')
	
	for i in range(1, len(values)):
		min_diff = min(min_diff, values[i] - values[i - 1])
	
	return min_diff

이 부분은 문제에서 말하는 가장 작은 차를 구하는 부분이다.
min_diff 는 float(‘inf’) 를 사용하는데 그냥 무한한 수라고 보면 된다.
음의 무한대는 float(‘-inf’) 참고로 int에는 불가능하다고 한다.

시간 복잡도와 공간 복잡도

시간 복잡도:
- inorder_traversal 함수를 호출하여 BST를 중위 순회하면서 모든 노드 값을 얻는다. 중위 순회는 BST의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N) 다. 여기서 N은 BST의 노드 수다.
- 중위 순회 후, 모든 값에 대한 최소 차이를 계산하는 루프가 있으며, 이 루프는 모든 노드 값을 한 번씩 비교하므로 O(N) 시간이 소요된다.
- 따라서 전체 시간 복잡도는 O(N) 다.
공간 복잡도:
- inorder_traversal 함수에서 재귀적으로 호출되는 스택 프레임에 대한 공간이 소비된다. 이 스택 프레임은 BST의 높이에 비례하며, 일반적으로 O(log N) 다. 하지만 트리가 불균형하거나 스택 제한이 있다면 최악의 경우 O(N)의 공간이 필요할 수도 있다.
- 추가적으로 values 리스트가 중위 순회 결과를 저장하는데 사용되며, 이 리스트의 길이는 BST의 노드 수에 비례하므로 O(N)의 공간을 사용한다.
- 따라서 전체 공간 복잡도는 O(N) 다.

회고 과정

이제 막 이해를 해서 다른 사람들의 코드를 보면서 이해를 하는 시간을 좀 더 갖는 게 좋다고 생각했다.
- 다음 문제에서는 절대로 답을 보지 않을 생각이기 때문에..ㅜ
  다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

class Solution:
    def getMinimumDifference(self, root: Optional[TreeNode]) -> int:
        cur, stack, min_diff, prev_val = root, [], float('inf'), -float('inf')

        while stack or cur:
            while cur:
                stack.append(cur)
                cur = cur.left
            node: TreeNode = stack.pop()
            min_diff = min(min_diff, abs(node.val - prev_val))
            prev_val = node.val
            cur = node.right

        return min_diff

cur 은 root 그리고 stack 은 [] 기본 값이 False 다.

cur은 현재 노드를 가리키는 포인터다. 초기에는 root로 설정된다.
stack은 스택 자료구조로, BST를 중위 순회하기 위해 사용된다.
min_diff는 최소 차이를 저장하는 변수로, 무한대(infinity)로 초기화된다.
prev_val은 이전에 방문한 노드의 값을 저장하는 변수로, 음의 무한대(negative infinity)로 초기화된다.
내부 루프에서는 현재 노드(cur)를 왼쪽으로 계속 이동하면서 왼쪽 서브트리의 노드들을 스택에 차례로 추가한다. 이렇게 하면 가장 왼쪽 노드부터 차례대로 스택에 쌓이게 된다.
왼쪽 서브트리의 노드들을 스택에 추가한 후, 스택에서 하나의 노드를 꺼낸다. 이 노드를 node 변수에 할당한다.
현재 노드(node)와 이전에 방문한 노드의 값(prev_val)를 비교하여 두 노드 간의 차이를 계산하고, 최소 차이(min_diff)를 업데이트한다.
이전 노드의 값을 현재 노드의 값으로 업데이트한다.
현재 노드의 오른쪽 서브트리를 방문하기 위해 cur을 오른쪽 자식 노드로 이동한다.
BST의 중위 순회가 완료되면 최소 차이(min_diff)를 반환한다.

중위 순회를 반복문을 사용하여 구현한 효율적인 방법으로, BST의 모든 노드를 한 번 방문하면서 최소 차이를 계산한다.

시간 복잡도:
- 주어진 코드는 BST를 중위 순회하면서 두 인접한 노드 간의 최소 차이를 계산한다.
- 중위 순회는 BST의 모든 노드를 한 번씩 방문하므로 시간 복잡도는 O(N)다. 여기서 N은 BST의 노드 수다.
- 중위 순회를 수행하면서 두 인접한 노드 간의 차이를 계산하고 최소 차이를 업데이트하므로 각 노드에서 상수 시간이 소요된다.
- 따라서 전체 시간 복잡도는 O(N) 다.
공간 복잡도:
- 주어진 코드에서는 스택(stack)을 사용하여 중위 순회를 구현하고 있다. 스택에는 BST의 높이에 비례하는 공간이 필요하다. BST가 균형 잡힌 경우(평균적인 경우), 스택의 크기는 O(log N) 다. 하지만 BST가 불균형한 경우나 최악의 경우(모든 노드가 한 쪽으로 쏠린 경우) 스택의 크기는 O(N)이 될 수 있다.
- 추가적으로 변수 min_diff, prev_val, cur, node 등의 상수 공간이 사용된다.
- 따라서 전체 공간 복잡도는 O(N) 또는 O(log N) 다.

Twitter Facebook LinkedIn

[530. Minimum Absolute Difference in BST] (알고리즘)

문제

스스로 고민

접근법

중위 순회가 뭘까?

구현 코드

깨달은 점!

시간 복잡도와 공간 복잡도

회고 과정

다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고

공유하기

댓글남기기

참고

[알고리즘] 숫자의 표현

[알고리즘] 체육복

[알고리즘] 둘만의 암호

[알고리즘] 완주하지 못한 선수