Leetcode
[Leetcode] 230. Kth Smallest Element in a BST - JS
Wix
2024. 11. 30. 10:00
1. 문제 분석
문제분석
--------------------
이진검색트리의 root와 정수 k가 주어질 때,
모든 노드 중에서 k번째로 작은 값을 반환하라.
제한조건
--------------------
- 1 <= k <= n <= 10^4
- 0 <= node.val <= 10^4
2. 접근 방법
접근방법
--------------------
중위순회하면 오름차순으로 순회가 가능하다.
각 노드 순회시마다 count값 증가하여 k번째와 동일한 node의 값을 반환한다.
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
* @param {number} k
* @return {number}
*/
var kthSmallest = function(root, k) {
let count = 1;
let res = -1;
function inorder(node) {
if (!node) return;
inorder(node.left);
if (res !== -1) {
return;
}
if (k === count) {
res = node.val
}
count++;
inorder(node.right);
}
inorder(root);
return res;
};
4. 복잡도 분석
- 시간복잡도: O(n)
- 공간복잡도: O(1)
중위 순회를 하여 이진 검색트리의 노드를 오름차순으로 순회한다.
각 노드를 순회할 때 마다 count 값을 증가시켜 k 와 동일할 때의 node 값을 저장한다.
최적화를 위해 결과값이 변경되었을 때는 중위 순회를 종료한다.