[알고리즘] LeetCode - Kth Smallest Element in a BST

Kth Smallest Element in a BST - LeetCode

문제 설명

• 이진 탐색 트리의 root 노드가 주어진다.
• 이진 탐색 트리에서 k번째로 작은 수를 찾아서 반환해야 한다.
• 노드의 값은 0 이상이다.

문제 해결

• 중위 순회를 통해 오름차순으로 탐색했다.
• 이미 정답이 나온 경우 더이상 탐색하지 않도록 해 메모리 성능을 개선했다.
• root 기준 왼쪽 자식의 수가 root의 위치이기 때문에 정수형 변수 count를 이용해 root가 몇 번째인지 파악했다.
• 왼쪽을 탐색한 후 나온 count와 k와 비교하여 현재 root가 몇 번째로 작은 수인지 파악하고, 조건과 일치하면 정수형 변수 answer에 갱신했다.

시간 복잡도

• O(N) - 최악의 경우

풀이 코드

class Solution {
    static int answer;

    public int kthSmallest(TreeNode root, int k) {
        answer = -1;
        inOrder(root, 0, k);
        return answer;
    }

    static int inOrder(TreeNode root, int count, int k) {
        // 이미 답 나온 경우 더이상 탐색 안함
        if (answer > -1) {
            return count;
        }
        if (root == null) {
            return count;
        }
        // 왼쪽아래에 달린 자식 수
        count = inOrder(root.left, count, k);
        
        // root가 몇 번째 인지 나오죠?
        if (count == k - 1) {
            answer = root.val;
        }
        
        // root까지 해서 +1 한 후 오른쪽 탐색
        return inOrder(root.right, count + 1, k);
    }
}

결과

시간	메모리
0 ms	43.85 MB