[LeetCode] Minimum Absolute Difference in BST - Javascript

Minimum Absolute Difference in BST

[이진 탐색 트리, 가장 짧은 간격 찾기]

 

제약 조건 

The number of nodes in the tree is in the range [2, 10^4].
0 <= Node.val <= 10^5

Example

초기 문제 접근 방식

트리의 각각의 노드끼리 간격의 가장 작은 차이의 절댓값을 구하는 문제이다.

초기엔 서로 인접한 노드끼리에서만 간격 차이를 구하는 것으로 이해하여,
tmp 값에는 부모 노드의 값을 저장하고

tmp 값과 자식의 노드 왼쪽과 오른쪽을 빼기 연산을 하여 최솟값을 min 변수에 계속 저장하는 방식으로 코드를 작성했다.

recusive라는 함수를 생성해 tree 데이터를 받아 해당 데이터가 없으면 리턴을 한다.
그 후tmp 값과 data.val의 절댓값 차이를 구하고 min 값과 비교를 해 min에 저장한다.

 

data.left로 recusive 함수를 재귀 호출해 반복을 하고 data.left의 데이터가 null이면 데이터가 없다는 의미이기에,
왼쪽 연산 노드의 최솟값을 모두 구한 후 오른쪽 트리의 노드를 모두 호출해 반복해 min 값을 구한다.

 

위의 방식대로 풀이를 제출하면, 아래의 테스트 케이스에서 걸린다.
각각의 트리에 노드가 인접한 노드끼리의 간격이 아닌, 모든 노드 중 가장 작은 간격을 구하는 것이었다.

초기 접근 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
   let min = Number.MAX_SAFE_INTEGER;
   let tmp = -Infinity;

   const recursive = data => {
      if (!data) {
         return;
      }
      min = Math.min(min, Math.abs(tmp - data.val));
      tmp = data.val;
      recursive(data.left);
      recursive(data.right);
   };

   recursive(root);

   return min;
};

 

다시 생각 해보며

코드를 재작성하는데, 이전 코드와 큰 차이가 없었다.
recusive(data.left) 코드 한 줄을 위로 올려, 가장 왼쪽부터 모든 노드를 순회하도록 중위 순회를 하는 것이다.
이렇게 하면 이전 코드와 다르게 인접한 노드의 간격만 구하는 것이 아닌, 모든 노드의 간격의 최솟값을 구할 수 있었다.

이후 오른쪽 노드도 재귀 호출해 반복하여 최솟값을 구한다.

solve 코드

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */
/**
 * @param {TreeNode} root
 * @return {number}
 */
var getMinimumDifference = function (root) {
   let min = Number.MAX_SAFE_INTEGER;
   let tmp = -Infinity;

   const recursive = data => {
      if (!data) {
         return;
      }
      recursive(data.left);
      min = Math.min(min, Math.abs(tmp - data.val));
      tmp = data.val;
      recursive(data.right);
   };

   recursive(root);

   return min;
};