문제
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
Binary Search Tree가 주어진다. 여기서 각 값의 차이 중 가장 작은 값을 리턴한다.
풀이 1
각 노드의 값의 차이 중 가장 작은 값을 구하는 문제이다.
각 원소를 오름차순으로 정렬한 뒤 차이값을 구하여 풀어보려고한다.
1. 각 원소들을 우선순위 큐에 넣어 오름차순으로 만든다.
2. 큐에서 원소들을 꺼내가며 차이값을 구한다.
결과 1
class Solution {
// 오름차순 정렬을 위한 우선순위 큐
PriorityQueue<Integer> queue = new PriorityQueue<>();
public int getMinimumDifference(TreeNode root) {
insert(root);
// queue에서 원소들을 꺼내어 가며 최소값을 찾아준다.
int min = Integer.MAX_VALUE;
while (queue.size() > 1) {
int prev = queue.poll();
min = Math.min(min, queue.peek() - prev);
}
return min;
}
// 모든 노드를 넣기 위한 재귀 함수이다.
// 현재 노드의 값을 넣고 왼쪽, 오른쪽 노드의 값을 넣어 준다.
public void insert(TreeNode node) {
if (node == null) {
return;
}
queue.add(node.val);
insert(node.left);
insert(node.right);
}
}
차이값을 찾는 간단한 문제로, 위의 풀이로도 적절하게 문제를 풀 수 이었습니다.
하지만 해당 문제의 키워드는 '이진 탐색 트리'에 있습니다.
이진 탐색 트리에 대해 간단히 알아보고 이를 활용하여 문제를 풀어보겠습니다.
Binary Search Tree
BST는 이진 탐색 트리로, 각 노드의 왼쪽 하위 트리에는 해당 노드보다 작은 키를, 오른쪽 하위 트리에는 해당 노드 보다 큰 키를 가진 노드들만 존재합니다. 즉, 이미 정렬되어 있는 자료구조 입니다.
이진 탐색 트리의 탐색 방법은 아래와 같습니다.
- In Order Traversal 중위 순회
- 왼쪽 하위 트리 -> 현재 노드 -> 오른쪽 하위 트리 순으로 방문합니다.
- 오름차순으로 노드를 방문할 수 있습니다.
- 정렬된 순서대로 값을 가져오고 싶을 때 활용됩니다.
- Pre Order Traversal 전위 순회
- 현재 노드 -> 왼쪽 하위 트리 -> 오른쪽 하위 트리 순으로 방문합니다.
- 노드를 방문하는 순서대로 처리할 수 있습니다.
- 트리의 복제나 트리의 구조를 그대로 유지하면서 다른 작업을 해야할 때 활용됩니다.
- Post Order Traversal 후위 순회
- 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 현재 노드 순으로 방문합니다.
- 하위 트리들을 먼저 처리한 후 현재 노드를 처리하는 방식입니다.
- 트리의 노드를 삭제할 때, 하위 노드들을 먼저 삭제한 후 상위 노드를 삭제하는 경우에 활용됩니다.
- 계산식의 후위 표기법에 사용됩니다.
- Level Order Traversal 레벨순회
- 너비 우선 탐색 입니다.
- 시작 노드에서 가장 가까운 노드부터 차례대로 탐색하는 방법입니다.
- 시작 노드 부터 거리에 따라 레벨 별로 탐색합니다.
위의 탐색 방법 중 In Order Traversal 방식으로 탐색한다면 문제 풀이에 필요한 오름차순 탐색이 가능합니다.
다음 풀이에서는 중위 순회 방법으로 문제를 풀어보겠습니다.
풀이2
BST는 왼쪽 하위 트리에는 해당 노드보다 작은 키를, 오른쪽 하위 트리에는 해당 노드보다 큰 키를 저장합니다.
이를 활용하여 왼쪽 하위 노드와 부모 노드, 부모 노드와 오른쪽 노드 순서대로 각각의 차이를 구합니다.
1. 왼쪽 끝의 노드를 방문합니다.
2. 해당 노드를 기억합니다.
3. 부모 노드와 값의 차이를 구합니다.
4. 부모 노드를 기억합니다.
5. 오른쪽 노드와 값의 차이를 구합니다.
6. 오른쪽 노드를 기억합니다.
결과 2
class Solution {
TreeNode prevNode = null;
int min = Integer.MAX_VALUE;
public int getMinimumDifference(TreeNode root) {
inOrderTraversal(root);
return min;
}
public void inOrderTraversal(TreeNode node) {
if (node == null) {
return;
}
inOrderTraversal(node.left);
if (prevNode != null) {
min = Math.min(min, Math.abs(node.val - prevNode.val));
}
prevNode = node;
inOrderTraversal(node.right);
}
}
풀이 1에서는 이미 정렬되어 있는 자료구조를 우선 순위 큐를 사용하여 또 한번 정렬하였습니다.
이번 결과에서는 정렬하는 시간, 우선 순위 큐를 사용한 메모리를 줄일 수 있었습니다.
