문제

https://leetcode.com/problems/kth-smallest-element-in-a-bst/

해결 방법

• 530. Minimum Absolute Difference in BST 이 문제와 매우 유사한 문제
• k 번째 작은 수를 구할 때, 중위순회를 통해 작은 수부터 조회하면서 idx를 증가 시키고, idx가 k와 같으면 그 값을 return

코드

class Solution {

    static int answer;
    static int idx;

    public int kthSmallest(TreeNode root, int k) {
        idx = 0;
        find(root, k, false);
        return answer;
    }

    private void find(TreeNode now, int k, boolean finish) {
        if (finish) return;

        if (now.left != null) {
            find(now.left, k, finish);
        }

        idx ++;
        if (idx == k) {
            answer = now.val;
            finish = true;
            return;
        }

        if (now.right != null) {
           find(now.right, k, finish);
        }
    }
}

결과