LeetCode 530 - Minimum Absolute Difference in BST

Minimum Absolute Difference in BST - LeetCode

 

구해야 하는 값이 노드에 있는 값의 차이 중에 절댓값이 제일 작은 것이다.

가장 먼저 떠오르는 방법은 모든 트리를 탐색해서 값들을 저장하고 거기서 모든 값을 순회해 목푯값을 찾는 것이다.

이는 N개의 노드를 탐색하고 이중루프를 사용하기 때문에 결과적으로 O(N^2)의 시간복잡도를 가지게 될 것이다. 아주 비효율적이다.

 

다른 효율적인 방법을 생각해보자.

최소 절대 차이를 어떻게 효율적으로 찾을 수 있을까?

생각해봐야 할 점은 주어진 트리가 그냥 이진트리가 아니라 이진 탐색 트리(BST)라는 것이다.

BST는 왼쪽 노드는 부모 노드보다 작고, 오른쪽 노드는 부모 노드보다 크다는 특징을 가지고 있다.

이 말은 중위순회를 사용하게 되면 노드 값이 정렬된 순서로 나열된다는 뜻이다.

그렇다면 모든 노드를 이중루프를 통해 확인할 필요 없이 인접한 값들끼리만 비교하면 될 것이다.

해야 할 일이 다음으로 정리됐다.

1. BST를 중위 순회하여 정렬된 노드 값을 얻는다.
2. 순회하면서 인접한 노드 간의 차이를 계산한다.

/**
 * 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 {
    public int getMinimumDifference(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        search(root, values);
        int min = Integer.MAX_VALUE;
        int prev = values.get(0);

        for (int i = 1; i < values.size(); i++) {
            int val = values.get(i);
            min = Math.min(min, val - prev);
            prev = val;
        }

        return min;
    }

    private void search(TreeNode node, List<Integer> values) {
        if (node == null) return;

        search(node.left, values);
        values.add(node.val);
        search(node.right, values);
    }
}