[LeetCode 783] Minimum Distance Between BST Nodes (Java)

🚀 문제 분석

• 목표: BST 내의 임의의 두 노드 값의 차이 중 최솟값을 찾습니다.
• 핵심: 모든 노드를 전수 비교($O(N^2)$)하지 않고, BST의 정렬 속성을 이용해 후보군을 어떻게 압축할 것인가가 포인트입니다.

💡 해결 전략: 중위 순회(In-order)를 통한 전수 커버

단순히 한 시점의 비교가 아니라, 순회 과정에서 모든 인접한 노드 간의 거리를 측정하는 것이 전략입니다.

1. BST의 중위 순회: Left -> Root -> Right 순서로 방문하면 모든 노드 값은 오름차순 수열이 됩니다.
2. 인접 노드의 연속적 비교: 수열 상에서 $a$와 $b$의 차이가 최소가 되려면, $a$와 $b$는 반드시 정렬된 수열에서 붙어 있어야 합니다.
3. 좌우 서브트리 커버:
   • 현재 노드 입장에서 왼쪽 서브트리의 가장 큰 값은 중위 순회상 바로 직전(prev)에 방문하게 됩니다.
   • 반대로 오른쪽 서브트리의 가장 작은 값은 현재 노드를 prev로 두고 바로 다음에 방문하게 됩니다.
   • 결국 순회를 완료하면 모든 노드에 대해 좌우 인접 노드와의 차이를 전부 계산하게 되어 최솟값이 누락될 수 없습니다.

💻 구현 코드 (Java)

public class Solution_Leetcode_783 {

    // 이전 노드의 값을 저장하여 연속적인 비교 흐름을 유지
    private Integer prev = null;
    // 탐색 과정에서 발견된 최소 차이를 실시간 갱신
    private int min = Integer.MAX_VALUE;

    public int minDiffInBST(TreeNode root) {
        inorder(root);
        return min;
    }

    private void inorder(TreeNode node) {
        if (node == null) {
            return;
        }

        // 1. 왼쪽 서브트리 끝까지 탐색
        inorder(node.left);

        // 2. 현재 노드와 직전 노드(왼쪽 서브트리의 최댓값) 비교
        if (prev != null) {
            // 정렬된 흐름 속에서 인접한 두 값의 차이를 추출
            min = Math.min(min, node.val - prev);
        }
        // 현재 노드 값을 다음 노드 비교를 위한 '직전 값'으로 전달
        prev = node.val;

        // 3. 오른쪽 서브트리 탐색 (이 과정에서 현재 노드는 오른쪽 자식의 prev가 됨)
        inorder(node.right);
    }
}

🧐 기술적 고찰: 왜 이 '흐름'이 완벽한가?

• 좌우 경계의 완벽한 탐색: 중위 순회는 루트를 기준으로 왼쪽 서브트리의 우측 끝(최댓값) -> 루트 -> 오른쪽 서브트리의 좌측 끝(최솟값) 순으로 흐릅니다. 이 과정에서 루트는 자신의 양옆 서브트리와 가장 가까운 값들을 모두 한 번씩 만나게 됩니다.
• $O(N)$의 효율성: 굳이 모든 노드 쌍을 대조해 보지 않아도, 정렬된 선형 흐름을 따라가는 것만으로도 수학적으로 가장 가까운 후보들만 골라낼 수 있습니다.
• 상태 추적의 연속성: prev 멤버 변수는 재귀의 층위를 무시하고 오직 방문 순서에만 의존합니다. 이는 트리의 복잡한 구조를 단 하나의 일관된 선형 데이터 흐름으로 치환하여 문제를 단순화하는 강력한 도구가 됩니다.