[Java] 230. Kth Smallest Element in a BST

문제 파악

k번째로 작은 값을 출력해야한다.

 

---

풀이

1️⃣ 중위 순회를 이용한 풀이

💡 떠오른 Idea

트리 구조에서 중위 순회를 하면 오름차순 순서로 노드 데이터를 출력할 수 있다.

이러한 원리를 적용하여 k번째 노드에 접근했을 때, 값을 저장하도록 구현하면 되겠다고 판단하였다.

 

class Solution {
    int ans = 0;
    int idx = 1;

    public int kthSmallest(TreeNode root, int k) {
        inOrder(root, k);
        return ans;
    }

    private void inOrder(TreeNode node, int k) {
        if (node == null) {
            return;
        }

        inOrder(node.left, k);

        if (idx == k) {
            ans = node.val;
        }

        idx++;

        inOrder(node.right, k);
    }
}

 

결과

---

📖 회고

이전에 해결했던,

Minimum Absolute Difference in BST - LeetCode

 

이 문제와 풀이 방식이 거의 동일해서 쉽게 해결할 수 있었다.