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.

풀이

• abs(node1.val - node2.val)의 최솟값을 구하는 문제
• Tree를 inorder로 탐색하게 되면 오름차순으로 순회할 수 있다.
• root의 값과 이전 노드의 값의 차이를 구하여 갱신한다.

수도 코드

dfs(node):
	if node가 null이라면:
    	return
    # inorder
    dfs(node.left)
    if 이전에 탐색한 값이 있다면:
    	answer = min(answer, node.val - prev.val)
    prev = node
    dfs(node.right)

Solution(Runtime: 0ms)

class Solution {
    int answer;
    TreeNode prev;

    void dfs(TreeNode node) {
        if (node == null) {
            return;
        }

        dfs(node.left);
        if (prev != null) {
            answer = Math.min(answer, node.val - prev.val);
        }
        prev = node;
        dfs(node.right);
    }
    public int getMinimumDifference(TreeNode root) {
        answer = 100_001;
        prev = null;
        dfs(root);
        return answer;
    }
}

왜 inorder로 탐색하냐면, 주어진 예제를 inorder로 순회했을 때의 순서는 1, 2, 3, 4, 6와 같다. 당연히, 앞 뒤로 붙어있는 숫자의 차이에서 최솟값이 나올 것이다.