[LeetCode Top Interview 150][Binary Search Tree (BST)] 530. Minimum Absolute Difference in BST

[LeetCode Top Interview 150]

[문제 링크]

[Binary Search Tree (BST)] 530. Minimum Absolute Difference in BST

[문제 설명]

Binary Search Tree (BST)의 root가 주어졌을 때,
트리에 있는 두 개의 다른 노드 간의 최소 절대 차이를 반환하여라

[예시1]

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

[예시2]

Input: root = [1,0,48,null,null,12,49]
Output: 1

[제약]

The number of nodes in the tree is in the range [2, 104].
0 <= Node.val <= 105

[내가 생각해본 방법]

이진 탐색 트리(BST)는 트리를 구성하는 노드의 자식이 최대 두 개인 트리를 의미한다. 사실 아직 이해가 잘 안가는 부분들이 많아서.. BST의 특징을 다시 정리하고, 문제 해결 방법과 다른 사람들의 풀이를 찾아보고 이해하려고 노력했다.

BST의 특별한 규칙은 왼쪽 하위 노드들은 root 노드보다 값이 작고,
오른쪽 하위 노드들은 root 노드보다 값이 크거나 같다는 것이다.

그렇다면 왼쪽 하위 노드 중에서 가장 큰 값이 root 노드의 이전 값에 해당될 것이고, 오른쪽 하위 노드 중에서 가장 작은 값이 root 노드의 다음 값에 해당될 것이다.

root 노드의 이전 값 : 왼쪽 하위 노드 중 가장 큰 값
root 노드의 다음 값 : 오른쪽 하위 노드 중에서 가장 작은 값

이 특징을 잘 이해하고 문제에 접근하는 것이 관건이라고 생각했다.

최대값과 최소값 구하기
root 노드부터 특정 노드의 오른쪽 노드가 없다면, 해당 노드가 해당 트리의 최대가 된다. 반대로 root 노드부터 특정 노드의 왼쪽 노드가 없다면 해당 노드가 해당 트리의 최소가 된다.

[의사 코드]

	최소값 차이 = Integer.최대값;
	이전 노드 = null; 

	최종 결과 (트리노드 root) {
    	최소값 차이 찾는 재귀 함수(root);
    	return 최소값;
	}

	void 최소값 차이 찾는 재귀 함수(트리노드 root)
		if(root가 존재한다면)
    		최소값 차이 찾는 재귀 함수(왼쪽 서브 트리 순회);
    	if(이전 노드가 존재한다면)
    		최소값 = 최소값 비교(최소값, 절대값(현재 노드값 - 이전 노드값));
    		이전 노드 = root;
    		최소값 차이 찾는 재귀 함수(오른쪽 서브 트리 순회);
    	return ;

[작성 코드]

class Solution {

    int minDiff = Integer.MAX_VALUE;
    TreeNode prev = null;

    public int getMinimumDifference(TreeNode root) {
        find(root);
        return minDiff;
    }

    public void find(TreeNode root) {
        if (root != null) {
            find(root.left);
            if (prev != null)
                minDiff = Math.min(minDiff, Math.abs(root.val - prev.val));
            prev = root;
            find(root.right);
        }
        return;
    }
}