530. Minimum Absolute Difference in BST

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

문제 출처

Minimum Absolute Difference in BST - LeetCode

[처음 생각한 접근 방법]

두 노드의 값의 차가 가장 작을 때 그 값을 리턴하라.

생각 나는 아이디어가 없어서 BFS로 노드를 모두 탐색하고, 정렬한 후에 각각 비교하는 식으로 작성했다.

class Solution {
    public int getMinimumDifference(TreeNode root) {
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        List<Integer> list = new ArrayList<>();

        while (!q.isEmpty()) {
            TreeNode temp = q.poll();
            list.add(temp.val);
            
            if (temp.left != null) q.offer(temp.left);
            if (temp.right != null) q.offer(temp.right);
        }
        
        Collections.sort(list);
        int firstNumber = list.get(0);
        int diffrence = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); i++) {
            diffrence = Math.min(list.get(i) - firstNumber,diffrence);
            firstNumber = list.get(i);
        }
        
        return diffrence;
    }
}

[리트코드 답안]

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

}

중위순회를 이용한 방법이라고 하는데 얼마 전에 자료구조에서 본 건데 기억이 애매하다.

자료구조 복습을 다시 꾸준히 해야겠다.