Minimum Absolute Difference in BST

https://leetcode.com/problems/minimum-absolute-difference-in-bst

평가

결과 : 1번 실패 후 성공
풀이시간 : 16분

제출 결과 한 번 실패하긴 했으나, 어디에서 틀렸는지 보지 않고 문제 해결했습니다.

아이디어

쉬운 문제입니다.
원소들의 값 중 두 노드간의 값의 차이가 가장 작은 경우를 물어보는 문제입니다.

위 BST를 정렬된 배열 형태로 나타내면 아래와 같습니다.
[0,1,12,48,49]

이 배열을 기준으로 나랑 인접한 값들이 얼마나 차이나는지 확인해야 하는데요.

예를 들어 12의 경우, 어떻게 자신의 앞에 있는 값이 1이라는 걸 알 수 있을까요?

바로,,, BST의 전제를 생각해서 문제를 풀면 12의 앞에 붙어있는게 1이라는 걸 쉽게 찾을 수 있습니다.
BST의 전제는 다음과 같습니다.

1. 왼쪽 SubTree는 모두 parent의 value보다 작다.
2. 오른쪽 SubTree는 모두 parent의 value보다 크다.

위 정리를 이번 문제 풀이에 적용하면

왼쪽 SubTree로 이동하면 오른쪽에 인접한 값을 갱신할 수있고,
오른쪽 SubTree로 이동하면 왼쪽에 인접한 값을 갱신할 수 있다
는 이야기가 됩니다.

1에서 48로 오른쪽 SubTree로 이동하는 상황입니다.
자식을 확인하지 않은 상태에서 1과 48은 인접한 상태가 됩니다.
[1,48]

만약 48에서 12로 이동하면, 왼쪽 SubTree로 이동하는거니까 오른쪽에 인접한 값을 갱신할 수 있습니다.
48 기준 오른쪽에 인접한 값은 null이었는데 12에서는 48이 들어갑니다.
[1,12,48]

만약 48에서 49로 이동하면, 오른쪽 SubTree로 이동하는 거니까 왼쪽으로 인접한 값을 갱신할 수 있습니다.
[1,12,48,49]

이렇게 왼쪽으로 인접한 노드, 오른쪽으로 인접한 노드를 찾아 가장 짧은 거리를 계산하는 문제였습니다.

간단한 문제라 수도코드는 생략하고, 바로 코드로 보여드리겠습니다.

정답 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int getMinimumDifference(TreeNode root) {
        return findMinDifference(root, null, null);
    }

    int findMinDifference(TreeNode root, Integer nearestLeft, Integer nearestRight) {
        // 미니멈 계산하기
        int answer = 10000000; 
        if (nearestLeft != null) {
            answer = Math.min(answer, Math.abs(root.val - nearestLeft));
        }
        if (nearestRight != null) {
            answer = Math.min(answer, Math.abs(root.val - nearestRight));
        }
        
        if (root.left != null) {
            // 왼쪽이동
            answer = Math.min(answer, findMinDifference(root.left, nearestLeft, root.val));
        }

        if (root.right != null) {
            // 오른쪽이동
            answer = Math.min(answer, findMinDifference(root.right, root.val, nearestRight));
        }

        return answer;
    }
}