LeetCode 230: BST에서 k번째로 작은 값 찾기
중위 순회에 방문 횟수를 더했습니다
이진 탐색 트리와 정수 k가 주어질 때, k번째로 작은 노드의 값을 반환하는 문제입니다.
바로 앞의 최소 차이 문제에서 사용한 중위 순회를 그대로 활용했습니다. 왼쪽, 현재 노드, 오른쪽 순으로 방문하면 작은 값부터 읽게 됩니다.
가장 왼쪽 노드부터 값을 방문할 때마다 count를 늘립니다. count == k가 되는 순간의 값을 result에 저장하고 순회가 끝나면 반환합니다.
코드
아래 코드는 문제에서 제공하는 TreeNode를 사용합니다. 값을 찾아 result에 저장한 뒤에도 탐색을 바로 종료하지 않고 남은 노드까지 방문합니다.
public class Solution {
int count = 0;
int result = 0;
public int kthSmallest(TreeNode root, int k) {
inorder(root, k);
return result;
}
private void inorder(TreeNode root, int k) {
if (root == null) return;
inorder(root.left, k);
count++;
if (count == k) result = root.val;
inorder(root.right, k);
}
}