530. Minimum Absolute Difference in BST

이진 탐색 트리(Binary Search Tree, BST)의 루트 노드가 주어졌을 때, 트리 내의 어떤 두 다른 노드 값 사이의 최소 절대 차이를 반환하는 문제입니다.

예제:

• 예제 1: 입력으로 root = [4,2,6,1,3]이 주어지면, 출력은 1입니다.
• 예제 2: 입력으로 root = [1,0,48,null,null,12,49]이 주어지면, 출력은 1입니다.

제약 조건:

• 트리의 노드 수는 범위 [2, 10^4] 내에 있습니다.
• 0 <= Node.val <= 10^5

이진 탐색 트리의 특성을 이해하고 이를 활용합니다.
이진 탐색 트리에서는 왼쪽 자식 노드의 값이 부모 노드의 값보다 작고, 오른쪽 자식 노드의 값이 부모 노드의 값보다 크다는 특성을 이용하면 됩니다. 이 특성을 이용하면 트리를 중위 순회(in-order traversal)하면서 각 노드와 이전 노드의 차이를 계산하여 최소 절대 차이를 찾을 수 있습니다. 이 방법을 사용하면 시간 복잡도는 O(n)이 됩니다.
여기서 n은 트리의 노드 수입니다. 이 방법은 공간 복잡도도 O(n)이지만, 재귀를 사용하지 않고 스택을 사용하여 중위 순회를 구현하면 공간 복잡도를 O(h)로 줄일 수 있습니다. 여기서 h는 트리의 높이입니다.
이진 탐색 트리의 경우, 트리의 높이는 log(n)이므로 이 방법이 더 효율적일 수 있습니다.

public class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;
    public TreeNode(int x) { val = x; }
}

public class Solution {
    private TreeNode prev;
    private int minDiff = int.MaxValue;

    public int GetMinimumDifference(TreeNode root) {
        InOrder(root);
        return minDiff;
    }

    private void InOrder(TreeNode node) {
        if (node == null) return;

        InOrder(node.left);

        if (prev != null) {
            minDiff = Math.Min(minDiff, node.val - prev.val);
        }
        prev = node;

        InOrder(node.right);
    }
}

 InOrder라는 보조 메서드를 사용하여 트리를 중위 순회합니다. 중위 순회는 왼쪽 자식 노드 -> 부모 노드 -> 오른쪽 자식 노드 순서로 노드를 방문합니다. 이 방법을 사용하면 이진 탐색 트리의 노드들이 오름차순으로 방문되므로, 각 노드와 이전 노드의 차이를 계산하여 최소 절대 차이를 찾습니다. 

이진 탐색 트리 root = [4,2,6,1,3]에 대해 중위 순회를 실행하면 다음과 같은 순서로 노드를 방문하게 됩니다:

루트 노드인 4에서 시작합니다.
루트 노드의 왼쪽 자식 노드인 2로 이동합니다.
2의 왼쪽 자식 노드인 1로 이동합니다. 1은 더 이상 왼쪽 자식 노드가 없으므로 1을 방문합니다.
1의 부모 노드인 2로 돌아와서 2를 방문합니다.
2의 오른쪽 자식 노드인 3로 이동하여 3을 방문합니다.
3의 부모 노드인 2와 그의 부모 노드인 4로 돌아와서 4를 방문합니다.
4의 오른쪽 자식 노드인 6으로 이동하여 6을 방문합니다.
따라서, 이진 탐색 트리의 중위 순회 결과는 [1, 2, 3, 4, 6]이 됩니다.
이 순서대로 노드를 방문하면서 각 노드와 이전 노드의 차이를 계산하여 최소 절대 차이를 찾습니다.
이 경우, 최소 절대 차이는 1입니다.