[3주차] 530. Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst/?envType=study-plan-v2&envId=top-interview-150 

Minimum Absolute Difference in BST - LeetCode

---

📝 문제

BST의 루트 노드가 주어진다. 트리의 두 노드의 값 중, 최소 절댓값을 리턴하라.

 

 

🎈 풀이

BST 는 특정 부모 노드의 왼쪽 자식노드는 부모 노드보다 작거나 같고, 오른쪽 자식 노드는 부모 노드보다 크거나 같다.

즉, 어떤 서브트리의 루트 노드와 최소 절댓값을 가지는 노드는 루트 노트의 왼쪽 자식 서브트리의 가장 오른쪽 노드이다.

 

하지만 이 방법은 BST 의 정의에 따라 약간 달라질 수 있다. 문제는 두 노드가 동일한 값을 가질 때 나타난다.

보편적으로, BST는 동일 값을 허용하지 않거나, 동일 값인 경우 왼쪽 자식 서브트리로 보낸다. 하지만 해당 문제에서는 동일 노드 값을 어떻게 처리하는지 나와있지 않다.

동일 노드 처리를 우측 자식으로 정할 경우

 

따라서 트리 순회만으로 최소 절댓값을 찾는 방법은 포기하였고, 트리를 Pre-Order 방식으로 탐색하며 오름차순으로 정렬된 배열을 하나 만들었고, 슬라이딩 윈도우 방식으로 순회하며 최소 절댓값을 찾았다.

 

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    int min = Integer.MAX_VALUE;

    public int getMinimumDifference(TreeNode root) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        int min = Integer.MAX_VALUE;
        
        toList(root, list);

        for (int i=1; i<list.size(); i++) {
            min = Math.min(min, Math.abs(list.get(i-1) - list.get(i)));
        }

        return min;
    }

    private TreeNode toList(TreeNode node, ArrayList<Integer> list) {
        if (node == null) return null;

        toList(node.left, list);
        list.add(node.val);
        toList(node.right, list);

        return node;
    }
}

 

 

📈 타 솔루션 참고

시간복잡도: O(n)

공간복잡도: O(n)

class Solution {
    private int minDiff = Integer.MAX_VALUE;
    private TreeNode prev = null;
    
    public int getMinimumDifference(TreeNode root) {
        inorderTraversal(root);
        return minDiff;
    }
    
    private void inorderTraversal(TreeNode node) {
        if (node == null) {
            return;
        }
        
        inorderTraversal(node.left);
        
        if (prev != null) {
            minDiff = Math.min(minDiff, node.val - prev.val);
        }
        prev = node;
        
        inorderTraversal(node.right);
    }
}

 

처음에 문제 해결을 구상할 당시

 

이런 비교 상황을 염두하고 있었다. 하지만 중위 순회 탐색은 10의 바로 이전 노드가 9가 되기 때문에 바로 이전 노드만 기록한다면 문제가 없다.

 

그리고 요즘 PS하며 꺠닫는 거지만 클래스 멤버변수를 선언하여 전역변수 처럼 사용하는 것을 피할 필요가 없는 것 같다.

일반적인 상황에서 단순히 메서드 파라미터를 줄이기 위해 사용하는 방법은 당연히 안되겠지만 ps는 시간싸움 이기 때문에 이런 식으로 빠르게 코딩하는 것이 좋아보인다.