[Java] 530. Minimum Absolute Difference in BST

문제 파악

트리 안에 존재하는 임의의 두 노드의 차 중 최솟값을 반환해야한다.

 

---

풀이

1️⃣ 중위 순회를 이용한 풀이

💡 떠오른 Idea

노드 구조에서 중위 순회를 하면서 노드 값을 출력하면 오름차순으로 정렬된 데이터를 얻을 수 있다는 특징을 이용하였다.

첫번째 노드는 이전 노드가 존재하지 않으므로, 계산을 생략한다. 그리고 이전 노드 값에 기록해준다.

두번째 노드에 도달했을 때, 이전 노드 값과의 차이를 구하고 갱신한다. 갱신 후, 이전 노드 값에 두번째 값을 기록해준다.

....

위 과정을 반복하는 방식이다.

 

 

class Solution {
    int ans = Integer.MAX_VALUE;
    Integer prev = null;

    public int getMinimumDifference(TreeNode root) {
        inOrder(root);
        return ans;
    }

    public void inOrder(TreeNode node) {
        if (node == null) {
            return;
        }
        inOrder(node.left);

        if (prev == null) {
            prev = node.val;
        } else {
            ans = Math.min(ans, Math.abs(prev - node.val));
            prev = node.val;
        }

        inOrder(node.right);
    }
}

 

결과

---

📖 회고

그동안 TreeSet 이나 TreeMap 같은 정의된 자료구조만 사용했었다.

 

이번 문제는, 트리의 원리를 잘 파악하고 있지 않으면 해결할 수 없는 문제였다.

 

이번 문제를 해결하기 위해서, 트리의 정의와 원리를 다시 찾아보게 되었고

 

따라서 좋은 문제라고 생각한다.