LeetCode 530: BST 중위 순회로 가장 작은 차이 찾기

작은 값부터 방문하면 비교가 단순해집니다

이진 탐색 트리에서 서로 다른 두 노드를 골라 값의 차이를 구하고 그 절댓값 중 가장 작은 것을 찾는 문제입니다.

이진 탐색 트리의 구조부터 생각했습니다. 왼쪽에는 작은 값이, 오른쪽에는 큰 값이 있습니다. 그래서 전체를 어떤 순서로 방문하느냐가 중요했습니다. 왼쪽, 현재 노드, 오른쪽 순서로 방문하는 중위 순회를 사용하면 값을 오름차순으로 읽을 수 있습니다.

예시에서는 1 → 2 → 3 → 4 → 6 순서로 방문합니다. 정렬된 값 사이의 가장 작은 차이는 이웃한 값에서 찾을 수 있어서 직전에 방문한 값만 기억하면 됩니다.

prev는 이전 값이고 minDiff는 지금까지의 최소 차이입니다. 첫 노드에서는 비교할 이전 값이 없어 건너뛰고 이후에는 root.val - prev로 차이를 구해 최솟값을 갱신합니다. 방문 순서가 오름차순이어서 차이는 음수가 되지 않습니다.

코드

아래는 제출 코드입니다. 문제에서 제공하는 TreeNode를 사용합니다.

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);
    }
}