[LeetCode/JAVA] 230. Kth Smallest Element in a BST

문제

이진 탐색 트리가 주어질 때, 정수 K가 주어지고 이진 탐색 트리에서 K번째로 작은 노드의 값을 출력하는 문제이다.

풀이

이전 최소 차이값을 찾는 문제와 동일하다.

중위 탐색을 사용하면 오름차순으로 조회가 가능하기 때문에, 제일 왼쪽 루트부터 시작해서 count를 증가시키면서 주어진 k와 같을 때 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);
    }
}