[leetcode - BST / Java] 530. Minimum Absolute Difference in BST

1. 문제

---

- 주어진 노드에서 Binary Search Tree를 사용하여 최솟값을 찾아라

2. 의사코드

---

Binary Search Tree에서 많이 사용하는 방법에는 크게 BFS, DFS 두 가지가 있다.

1. BFS(Breadth-First Search) - 너비 우선 탐색
   • 트리의 레벨별로 노드를 탐색하며 일반적으로 큐를 사용하여 구현한다.

2. DFS(Depth-First Search) - 깊이 우선 탐색
   • In-Order Traversal (중위 순회): 왼쪽 하위 트리를 먼저 탐색하고 -> 현재노드 -> 오른쪽 하위 트리 순서로 탐색하며 오름차순 정렬이다.
   • Pre-Order Traversal (전위 순회): 현재 노드 -> 왼쪽 하위 트리 -> 오른쪽 하위 트리를 탐색한다.
   • Post-Order Traversal (후위 순회): 왼쪽 하위 트리 -> 오른쪽 하위 트리 -> 현재 노드를 탐색한다.

이번 문제에서 사용할 방법은 DFS의 중위 순회이다.

1. 결과와 이전 노드의 값이 담길 전역변수 선언 (상태를 유지하기 위해) 
    Integer min = Integer.MAX_VALUE; // 출력용
    Integer data = null; // 처음에는 int data로 설정했지만 재귀함수를 사용하며 조건문에 필요하여 Integer로 변경

2. 재귀함수 구현
    public void 재귀(TreeNode node) {
        재귀(node.left) // 왼쪽 하위 노드
        .
        .
        .
        재귀(node.right) // 오른쪽 하위 노드
    }

3. 

3. 시도

---

class Solution {
    Integer min = Integer.MAX_VALUE;
    Integer data = null;

    public int getMinimumDifference(TreeNode root) {
        repeatForSort(root);
        return min;
    }

    public void repeatForSort(TreeNode node) {
        if(node == null) return ; // 현재 노드가 null이면 재귀 종료
        repeatForSort(node.left);
        if(data != null) min = Math.min(min, node.val-data);
        data = node.val; // 이전 노드값
        repeatForSort(node.right);
    }
}