[이진 검색 트리 (BST)] LC #530 Minimum Absolute Difference in BST

문제 설명

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.

Example 1:

BST Example 1 
Input: root = [4,2,6,1,3]
Output: 1

Example 2:

BST Example 2 
Input: root = [1,0,48,null,null,12,49]
Output: 1

Constraints:


문제 링크: https://leetcode.com/problems/minimum-absolute-difference-in-bst/

1. 문제의 핵심: 이진 검색 트리(BST)의 속성 활용하기

이 문제는 이진 검색 트리(BST)의 가장 중요한 속성 하나를 알고 있는지 묻고 있습니다.

핵심 속성: BST를 중위 순회(In-order Traversal)하면, 노드 값들이 오름차순으로 정렬된 순서로 방문된다.

예를 들어, 예제 1의 [4,2,6,1,3] 트리를 중위 순회하면 1 → 2 → 3 → 4 → 6 순서가 됩니다. 최소 차이는 결국 이 정렬된 숫자들 중에서 서로 인접한 두 숫자 간의 차이 중 가장 작은 값이 됩니다. (즉, 2-1=1, 3-2=1, 4-3=1, 6-4=2 중 최소값은 1입니다.)

따라서, 모든 노드 쌍을 비교하는 O(N2)의 비효율적인 방법 대신, 중위 순회를 통해 O(N)으로 문제를 해결할 수 있습니다.

2. 해결 전략: 중위 순회와 상태 추적

알고리즘은 매우 간단합니다.

  1. 트리를 중위 순회(In-order)합니다. (왼쪽 서브트리 → 현재 노드 → 오른쪽 서브트리)
  2. 순회하면서 이전 노드의 값(prev)을 계속 기억해 둡니다.
  3. '현재 노드'를 방문할 때마다 현재 노드 값 - 이전 노드 값을 계산하여 최소 차이(minDiff)를 갱신합니다.
  4. '현재 노드' 처리가 끝나면, 다음 노드를 위해 이전 노드 값을 '현재 노드 값'으로 업데이트합니다.

3. Java 코드 구현 (중위 순회)

재귀를 이용한 중위 순회로 이 로직을 깔끔하게 구현할 수 있습니다. 재귀 호출 전반에 걸쳐 `prev`와 `minDiff` 값을 유지하기 위해 클래스 멤버 변수를 사용합니다. 

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 직전 노드의 값을 저장할 변수. Integer 래퍼 타입을 사용해 null로 초기화.
    private Integer prev = null;
    // 최소 차이를 저장할 변수. 최댓값으로 초기화.
    private int minDiff = Integer.MAX_VALUE;

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

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

        // 1. 왼쪽 서브트리 순회
        inorder(node.left);

        // 2. 현재 노드 처리
        if (prev != null) {
            // 이전 노드가 존재하면, 현재 노드와의 차이를 계산하여 최소값 갱신
            minDiff = Math.min(minDiff, node.val - prev);
        }
        // 현재 노드의 값을 prev로 업데이트
        prev = node.val;

        // 3. 오른쪽 서브트리 순회
        inorder(node.right);
    }
}

💡 코드 세부 포인트