[Leetcode] 230. Kth Smallest Element in a BST - JS

https://leetcode.com/problems/kth-smallest-element-in-a-bst/description/?envType=study-plan-v2&envId=top-interview-150

 

 

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 값을 저장한다.

최적화를 위해 결과값이 변경되었을 때는 중위 순회를 종료한다.