Leetcode Top Interview 150] 530. Minimum Absolute Difference in BST

난이도 : easy

문제링크

• Binary Search Tree의 root 노드가 주어진다
• 노드들중 가장 작은 차이값을 리턴하라
• 노드의 수는 2~10^4 범위내에 있다
• 0 <= Node.val <= 10^5

 

1. 접근법

• 트리의 min(root - predecessor, successor - root) 값을 answer와 비교하여 answer 갱신
• 방문할 노드 없을 때까지 반복

2. 의사코드

3. 구현 코드

class Solution {    
    int answer = Integer.MAX_VALUE;
    Integer prev = null;
    public int getMinimumDifference(TreeNode root) {                    
        if (root.left == null && root.right == null) {            
            return 0;
        }            

        if (root.left == null) {            
            return root.right.val;
        }            

        if (root.right == null) {
            return root.left.val;
        }            

        int predecessor = getMinimumDifference(root.left);
        answer = Math.min(answer, root.val-predecessor);

        int successor = getMinimumDifference(root.right);
        answer = Math.min(answer, successor-root.val);

        return answer;
    }        
}

• 동작이 안된다
• successor를 리턴하지 않음 (오작동)

 

6. 회고

class Solution {    
    int minDifference = Integer.MAX_VALUE;
    Integer prev = null;
    public int getMinimumDifference(TreeNode root) {                    
        if (root == null) {
            return 0;
        }            

        getMinimumDifference(root.left);

        if (prev != null) {
            minDifference = Math.min(minDifference, root.val-prev);
        }

        prev = root.val;

        getMinimumDifference(root.right);

        return minDifference;
    }        
}

출처 : AlgorithmMadeEasy(youtube)

 

• BST를 중위순회식으로 순회하면 정렬된 순서로 방문할 수 있다
• 정렬된 순서대로 (현재 노드-이전 노드)를 끝까지 방문하여 값을 업데이트한다 
• 재귀적으로 반복하면서 값을 업데이트한다

도저히 모르겠어서 해설을 보았다

나는 비교노드를 배열 기준으로 인접한 노드가 아닌 모든 노드를 대상으로 해야 한다 생각했다

그래서 답이 나오지 않았다.

그러나 다른 해설을 보았을때 모두 배열기준 인접한 노드를 대상으로 최소 차이값을 리턴하였다