[LeetCode/JAVA] 530. Minimum Absolute Difference in BST

문제

이진 탐색 트리(BST)가 주어질 때, 트리의 두 노드간 가장 작은 차이를 찾고 그 값의 절대값을 반환하는 문제이다.

풀이

가장 먼저 이진 탐색 트리라는 형태를 생각했을 때, 노드 구조가 왼쪽은 작은 값 오른쪽은 큰 값 중간은 왼쪽과 오른쪽 값의 중간이다.

가장 작은 값을 찾기 위해서는 트리의 전체를 순환해야 찾을 수 있다고 판단하고, 어떻게 돌아야 차이를 찾을 수 있을까 고민했을 때

중위 탐색을 하면 왼쪽 -> 중간 -> 오른쪽 순으로 탐색하는 점을 생각했다. 이렇게 될 경우 

예시 1의 경우 시작을 1로하여 순서대로 1-2-3-4-6 순으로 진행하게 될 것이므로 오름차순으로 조회가 가능하다.

코드

public class Solution {
    Integer prev = null;
    Integer minDiff = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        inorder(root);
        return minDiff;
    }

    private void inorder(TreeNode root) {
        if (root == null) return;
        inorder(root.left);
        if (prev != null) minDiff = Math.min(minDiff, root.val - prev);
        prev = root.val;
        inorder(root.right);
    }
}