[Leetcode] 530. Minimum Absolute Difference in BST - JS

https://leetcode.com/problems/minimum-absolute-difference-in-bst/description/?envType=study-plan-v2&envId=top-interview-150

 

 

1. 문제 분석

문제분석
--------------------
이진 검색 트리(BST)의 루트가 주어졌을 때, 트리 내의 두 노드 사이의 절대값 차이의 최솟값을 반환하라.

제한조건
--------------------
- 노드의 갯수는 2 ~ 10^4개이다.
- 0 <= node.val <= 10^5

 

2. 접근 방법

접근방법
--------------------
이진 검색 트리는 부모노드 기준 값이 작으면 왼쪽,
값이 크면 오른쪽 노드로 배치된다.

중위 순회를 사용하면 제일 값이 작은 값부터 오름차순으로 순회할 수 있다.
오름차순으로 순회 시 현재값과 이전 값의 차이를 비교하면서 최소 차이를 갱신해준다.

 

3. 코드

/**
 * 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 minDiff = Infinity;
    let prevVal = null;

    function inorder(node) {
        if (!node) return;

        inorder(node.left);

        if (prevVal !== null) {
            minDiff = Math.min(minDiff, Math.abs(node.val - prevVal));
        }
        prevVal = node.val;

        inorder(node.right);
    }

    inorder(root);
    return minDiff;
    
};

 

 

4. 복잡도 분석

- 시간복잡도: O(n)

- 공간복잡도: O(1)

 

이진 검색 트리 문제를 처음 접해봐서 어떻게 해야할지 감이 안왔다. 재귀 함수를 사용하여 중위 순회하면서 이전 값을 기억하여

현재값과 비교해주는 방법을 배웠다.

 

Claude AI를 통해 공부했다. 설명을 잘해주는 것 같다.