https://leetcode.com/problems/find-peak-element/?envType=study-plan-v2&envId=top-interview-150

530. Minimum Absolute Difference in BST

⭐ 문제

이진 탐색 트리 (BST)의 루트가 주어졌을 때, 트리 내에서 서로 다른 두 노드 값 간의 최소 절대 차이를 반환해야합니다

🤔 접근 방향

BST특성상 Inorder Traversal로 순회하면 노드가 작은 값부터 큰 값 순서로 방문됩니다. 현재 노드와 그 이전 노드의 값을 비교하여 두 값의 차이를 계산합니다. 이때 나온 차이를 최소 절대 차이로 업데이트합니다. 이러한 과정을 계속해서 모든 노드를 순회하면서 최소 절대 차이를 찾습니다.

✍️ 의사 코드

1. prevNode를 초기화하고 minDiff를 최대값으로 설정

2. 중위 순회를 통해 노드를 순회하면서
   2.1. 현재 노드와 이전 노드 간의 차이를 계산
   2.2. 이전 노드를 현재 노드로 업데이트
   2.3. 왼쪽 서브트리를 순회
   2.4. 오른쪽 서브트리를 순회

3. 최소 차이인 minDiff를 반환

✅ 나의 풀이

class Solution {
    private TreeNode prevNode;
    private int minDiff;

    public int getMinimumDifference(TreeNode root) {
        // 초기값 설정
        minDiff = Integer.MAX_VALUE;
        prevNode = null;
        
        // 중위 순회를 통해 노드를 방문하면서 최소 차이 계산
        inorderTraversal(root);
        
        return minDiff;
    }
    
    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        
        // 왼쪽 서브트리 순회
        inorderTraversal(node.left);
        
        // 현재 노드와 이전 노드 간의 차이 계산 및 업데이트
        if (prevNode != null) {
            minDiff = Math.min(minDiff, Math.abs(node.val - prevNode.val));
        }
        prevNode = node;
        
        // 오른쪽 서브트리 순회
        inorderTraversal(node.right);
    }
}

🖥️ 결과

Runtime 0ms