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를 통해 공부했다. 설명을 잘해주는 것 같다.
'Leetcode' 카테고리의 다른 글
[Leetcode] 98. Validate Binary Search Tree - JS (0) | 2024.12.01 |
---|---|
[Leetcode] 230. Kth Smallest Element in a BST - JS (0) | 2024.11.30 |
[Leetcode] 103. Binary Tree Zigzag Level Order Traversal - JS (0) | 2024.11.29 |
[Leetcode] 102. Binary Tree Level Order Traversal - JS (0) | 2024.11.28 |
[Leetcode] 637. Average of Levels in Binary Tree - JS (0) | 2024.11.27 |