[LeetCode] 230. Kth Smallest Element in a BST

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

Kth Smallest Element in a BST - LeetCode

이진 검색 트리의 루트와 정수 k가 주어졌을 때, 트리에 있는 모든 노드의 값 중 K번째로 작은 값을 반환합니다.

 

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

 

문제 접근

이번에도 트리의 탐색을 위해 inorder를 사용하였습니다.

이진 검색 트리에서 inorder탐색은 정렬된 노드 탐색을 가능하게 합니다.

 

우선 depth위치까지는 전부 탐색해야합니다.

class Solution {
    int k;
    int i;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        i = 0;
        inorder(root);
        return ret;
    }
 
    public void inorder(TreeNode root) {
        if (root == null) return;

        inorder(root.left);
        // self
        if (++i == k) {
            ret = root.val;
        }
        inorder(root.right);
    }
}

시간복잡도

모든 노드를 탐색하기 때문에 O(n)의 시간복잡도가 필요합니다.

 

하지만 조금 아쉽습니다.

문제에서 K를 주고있으니 K까지만 탐색하면 좋지 않을까? 라는 생각이 들었습니다.

 

시간복잡도 개선

확실한 차이가 있는 개선은 아니지만, 정해진 K까지만 탐색을 하면 즉시 종료하여

나머지 노드들은 탐색하지 않는 정도입니다.

 

만약 노드가 많다면 더 효율적이라고 생각이 됩니다.

 

i가 K와 일치하다면 ret에 현재 노드의 값을 저장하고 즉시 종료합니다. 

다른 노드를 재귀탐색하지 않기 위해 ret값이 변경되었다면 return하여

불필요한 재귀 탐색을 줄였습니다.

class Solution {
    int k;
    int i;
    int ret;
    public int kthSmallest(TreeNode root, int k) {
        this.k = k;
        inorder(root);
        return ret;
    }
 
    public void inorder(TreeNode root) {
        if (ret > 0) return;
        if (root == null) return;
        
        inorder(root.left);
        // self
        if (++i == k) {
            ret = root.val;
            return;
        }
        inorder(root.right);
    }
}

 

느낀점

정답이 맞는 코드라도 더 개선할 점이 있을까? 라는 생각을 계속 해야할것 같습니다.

 

참고

https://www.youtube.com/watch?v=I_R7RnOZxY0