[알고리즘] LeetCode - Minimum Absolute Difference in BST

Minimum Absolute Difference in BST - LeetCode

문제 설명

• 이진 탐색 트리의 root 노드가 주어진다.
• 이진 탐색 트리에서의 두 개의 노드 간 차의 절댓값 중 최솟값을 반환해야 한다.

문제 해결

• 오름차순으로 정렬되면 두 노드 간 차이를 쉽게 구할 수 있다.
• 이진 탐색 트리에서 중위 순회를 통해 오름차순으로 탐색할 수 있다.
• 왼쪽 자식을 탐색하고, 정수형 변수 pre의 값을 자신의 값으로 초기화한다.
• 탐색 순서는 왼쪽(가장 작은 값) - 중간 (중간 값) - 오른쪽 (가장 큰 값) 순이기 때문에 이전 값으로 계속 갱신하고, 첫 갱신 이후부터는 pre(이전 값)과 현재 값의 차를 계산하여 정수형 변수인 min을 최솟값으로 갱신한다.
• min을 반환한다.

시간 복잡도

• O(N)

풀이 코드

class Solution {
    static int min, pre;

    public int getMinimumDifference(TreeNode root) {
        min = Integer.MAX_VALUE;
        pre = Integer.MAX_VALUE;

        inOrder(root);

        return min;
    }

    static void inOrder(TreeNode root) {
        if (root == null) {
            return;
        }

        inOrder(root.left);
        if (pre != Integer.MAX_VALUE) {
            min = Math.min(min, root.val - pre);
        }
        pre = root.val;
        inOrder(root.right);
    }
}

결과

시간	메모리
0 ms	43 MB