LeetCode : 530. Minimum Absolute Difference in BST

문제 링크

문제 먼저 읽기

• 이진 검색 트리(BST)의 루트가 주어졌을 때, 트리에 있는 서로 다른 두 노드의 값 사이의 최소 차이 절대값을 반환합니다.

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

어떻게 풀까?

생각

주의! 처음에 문제를 잘못읽었었습니다. 역시 사람의 언어를 가장 잘해야 합니다 🥲

• 트리는 정렬 규칙상 인접 노드가 가장 그 차이가 적습니다.
• 그래서 인접하는 노드끼리 비교하면 안될까요?
• 재귀를 통해 BST 를 구현해봅시다.

수도코드

class Solution {
    TreeNode prev = null;
    int min = Integer.MAX_VALUE;
    
    public int getMinimumDifference(TreeNode root) {
        search(root);
        
        return min;
    }
    
    public void search (TreeNode node) {
        if (node == null) return;
        
        if (prev != null) { // 이전노드와 지금 노드 값 비교
            min = Math.min(min, Math.abs(prev.val-node.val));
        }
        prev = node;
        
        search(node.left);
        search(node.right);        
    }
}

• 근데 이 풀이는 testcase는 통과했으나 제출시 틀렸습니다.

Input
[236,104,701,null,227,null,911]
Output
123
Expected
9

• 알고보니 문제를 잘못읽었던 것인데요. 그래서 코드 순서가 중요했던 것입니다..
• “서로 다른 두 노드”의 차이를 비교해야하므로 이전 노드 업데이트를 해당 노트의 한쪽 노드 탐색이 모두 끝나고 하나씩 바꿔주는 방식으로 해야합니다.

결과

<aside> 💡 Success

Details

Runtime: 0 ms, faster than 100.00% of Java online submissions for Minimum Absolute Difference in BST.

Memory Usage: 43.4 MB, less than 24.82% of Java online submissions for Minimum Absolute Difference in BST.

</aside>

다른 풀이 방식과 문제 회고

• 공간 효율이 좋은 답변

class Solution {
    private int ans;
    private int prev;
    private int inf = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        ans = inf;
        prev = inf;
        dfs(root);
        return ans;
    }

    private void dfs(TreeNode root) {
        if (root == null) {
            return;
        }
        dfs(root.left);
        ans = Math.min(ans, Math.abs(root.val - prev));
        prev = root.val;
        dfs(root.right);
    }
}

• node가 아니라 값 그자체를 비교해서 메모리 사용을 극도로 줄인 답변이었습니다.