1. 문제 설명
- 트리의 루트와 정수 k가 주어졌을 때, 트리의 모든 노드 값 중에서 k번째로 작은 값을 (1부터 인덱스화하여) 반환합니다.
2. 접근 방법
- 이전 문제 530. Minimum Absolute Difference in BST
와 비슷하여 금방 풀 수 있었습니다.
- 이진 검색 트리에서 DFS 중위 탐색을 하면 오름차순 순으로 값을 조회하게 됩니다.
- 이 방법을 사용하여 이진 트리를
k만큼 카운트 하며 탐색하고 k번째 값을 반환할 변수 result에 저장합니다.
- 이진 트리 탐색 후 얻은 결과값은 반환하면 원하는 결과값을 얻을 수 있습니다.
3. 구현 코드
class Solution {
int count = 0;
int kk, result;
public int kthSmallest(TreeNode root, int k) {
kk = k;
inoderDfs(root);
return result;
}
public void inoderDfs(TreeNode node){
if(node != null){
inoderDfs(node.left);
count++;
if(count == kk)
result = node.val;
else
inoderDfs(node.right);
}
}
}
- 시간 복잡도 : O(n)
- 공간 복잡도 : O(log n)
5. 최종 회고
- 이전 문제와 비슷하여 다시 연습하는 느낌으로 풀었습니다. 간단하게 풀리어 다른 문제점을 만나지 못하여 아쉬웠지만 코드 효율도 괜찮은 것 같아 만족합니다.
