LeetCode-230 Kth Smallest Element in a BST 자바 풀이

Kth Smallest Element in a BST - LeetCode

문제

이진 탐색 트리 (BST)에서 K번째로 작은 요소를 반환하면 되는 문제입니다. 
이진 탐색 트리 답게 문제에서 예시로 들어준 트리도 정렬이 되어있기 때문에 어떤 순서로 탐색해야 효율적인지 고민해보면 됩니다.

풀이

K번째로 작은 요소를 찾는 문제이기 때문에 탐색을 가장 작은 데이터를 가진 노드부터 탐색하는 편이 좋습니다.

count라는 변수를 지정하여 탐색 시 마다 +1 한다 count가 K가 되었을 때 현재 탐색하고 있는 노드를 반환하면 됩니다.

중위 순회의 경우가 가장 작은 요소부터 탐색하는 경우이기 때문에 중위 순회를 사용하여 해결할 수 있습니다.

예1 >

[중위 순회 탐색 시] 1 -> 2-> 3-> 4 (1 번째로 작은 값: 1)

 

아래 실행 결과처럼 메모리 사용량이 좋지 않아서 개선할 수 있는 부분을 생각해보았습니다.

우선 count를 k로 대체하여 탐색시마다 count를 +1 하지 않고 k를 -1 한다면,

count라는 변수가 없이도 k가 0이 될 때 해당 노드의 값을 반환하도록 할 수 있을 것입니다.

마찬가지로 result 또한 result에 값을 저장하지 않고 바로 반환하여 대체할 수 있을 거라 생각이 듭니다.

이부분을 추후에 개선해 보도록 하곘습니다.

 

 

class Solution {
    int count;
    int result;
    public int kthSmallest(TreeNode root, int k) {
        inorder(root, k);
        return result;
    }
    private void inorder(TreeNode node, int k) {
        if (node == null) return;
        inorder(node.left, k);
        count++;
        if(count==k){
            result = node.val;
            return;
        }
        inorder(node.right,k);
    }
}