[Easy] LeetCode - no.530 Minimum Absolute Difference in BST : Java

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

 

 

문제

이진 탐색 트리(BST)의 root가 주어졌을 때, 노드들 사이의 최소 차이를 반환할 것

 

Example 1

 

 

 

 

Input: root = [4,2,6,1,3]
Output: 1

 

 

 

 

 

 

 

풀이1

    public int getMinimumDifference(TreeNode root) {
        List<Integer> values = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();

        queue.add(root);
        while(!queue.isEmpty()) {
            TreeNode cur = queue.poll();
            values.add(cur.val);

            if (cur.left != null) {
                queue.add(cur.left);
            }

            if (cur.right != null) {
                queue.add(cur.right);
            }
        }

        Collections.sort(values);
        int min = Integer.MAX_VALUE;

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

        return min;
    }

• BFS 활용
• List에 각 노드의 값을 add()한 후 Collections.sort() (오름차순 정렬)
• for문 내에서 Math.min()을 사용하여 최소 차이를 계산
• 시간복잡도 : O(N log N) (BFS 시간복잡도 = O(N), 정렬 시간복잡도 = O(N log N), for문 시간복잡도 = O(N))

💬 코드를 짜면서도 이건 아니다 싶었지만 오로지 통과하기 위해 만듦...

 

 

 

풀이2

참고

[LeetCode] 530. Minimum Absolute Difference in BST [JAVA(자바)]

    // BST + 중위순회 = 오름차순
    
    int minValue;
    Integer preValue;

    public int getMinimumDifference(TreeNode root) {
        minValue = Integer.MAX_VALUE;
        preValue = null;

        inorder(root);
        return minValue;
    }

    private void inorder(TreeNode root) {
        if (root == null) {
            return;
        }

        // left
        inorder(root.left);

        // self
        if (preValue != null) {
            minValue = Math.min(minValue, root.val - preValue);
        }
        preValue = root.val;

        //right
        inorder(root.right);
    }

• 이진 탐색 트리(BST)는 중위 순회 시 오름차순 정렬되어 있음
• preValue를 Integer로 선언 : null을 다루기 위함
• inorder()
  • 중위 순회 함수
  • 왼쪽 서브트리 처리
  • 노드 스스로 처리
    • preValue가 null이 아닐 경우 : 이전 값이 있으니 min 계산 가능 -> preValue 업데이트
    • preValue가 null일 경우 : 이전 값이 없으니 preValue 업데이트만 함
  • 오른쪽 서브트리 처리
• 시간복잡도 : O(N)