LeetCode-530 Minimum Absolute Difference in BST 자바 풀이

Minimum Absolute Difference in BST - LeetCode

문제

이진 탐색 트리(BST)에서 각 트리 안의 노드들의 값이 가장 적은 경우를 반환하는 문제입니다.  

풀이

1. 가장 차이가 적은 경우를 저장하기 위해 minDiff 라는 int형 변수를 생성합니다.

2. minDiff와 두 노드의 차이를 비교하여 더 적은 값을 저장하는 방식으로 진행할 예정이기에 minDiff에는 임시적으로 int가 가질 수 있는 최대 값을 저장합니다.

3. 현재 노드와 바로 전 노드의 차를 구하기 위해 prev 변수에는 바로 전 노드의 값을 저장합니다.

4. 임시로 prev 변수를 int가 가질 수 있는 최대 값을 저장하고, 이 값을 이용해 현재 탐색한 노드가 가장 처음의 노드인지 아닌지를 구별 할 수 있습니다.

5. 만약 현재 노드가 가장 처음 탐색한 노드라면 prev에 자기 자신을 저장하고 그 다음 노드로 탐색합니다. (오른쪽 노드)

6. 만약 prev에 값이 존재한다면(Interger.MAX_VALUE 가 아니라면) 현재 노드의 값과 prev의 차를 구하여 minDiff 와 비교후 더 적은 값을 minDiff에 저장합니다.

7. 트리를 전부 순회할 때까지 6번을 반복한다면 minDiff에는 가장 적은 차가 저장됩니다.  

class Solution {
    int minDiff = Integer.MAX_VALUE;
    int prev = Integer.MAX_VALUE;  
    public int getMinimumDifference(TreeNode root) {  
        minDiff = Integer.MAX_VALUE;  
        inorder(root);  
        return minDiff;  
    }  
  
    private int inorder(TreeNode root) {  
        if (root == null) {  
            return prev;  
        }  
        inorder(root.left);  
        if (prev != Integer.MAX_VALUE) {  
            minDiff = Math.min(minDiff, root.val - prev);  
        } 
        prev = root.val;
        return inorder(root.right);  
    }  
}