[BST] 530. Minimum Absolute Difference in BST

문제

Given the root of a Binary Search Tree (BST), return the minimum absolute difference between the values of any two different nodes in the tree.
 
Example 1:

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

Input: root = [1,0,48,null,null,12,49] Output: 1
 
Constraints:
The number of nodes in the tree is in the range [2, 10^4].
0 <= Node.val <= 10^5

문제접근

1. 트리를 순회하며 해당 트리의 값을 리스트에 추가한다.

2. 리스트를 정렬한다.

3. 리스트를 순회하며 최소값을 찾는다.

 

문제풀이

import java.lang.Math.*;

class Solution {

    static int min;
    public int getMinimumDifference(TreeNode root) {

        min = Integer.MAX_VALUE;
        
        List<Integer> list = new LinkedList<>();

        list.add(root.val);
        dfs(root, list);

        Collections.sort(list);

        int min = Integer.MAX_VALUE;


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

        return min; 
    }

    public void search(TreeNode node, List list){
        if(node.left != null ){
            list.add(node.left.val);
            search(node.left, list); 
        }
        if(node.right != null){
            list.add(node.right.val);
            search(node.right, list); 
        }
    }
}

 

다른풀이 및 회고

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

처음에 내가 고려헀던 방향하고 유사한 느낌이다.

리스트에 추가할 필요없이 트리를 순회하면서 계산하여 최솟값을 계산하면되는데 root를 제외하고 연산하며 테스트 케이스에서 실패가 나와서 내가 인지하지 못하는 케이스가 있다 생각하여 리스트를 만들어 추가하였었다.