[LeetCode] 230. Kth Smallest Element in a BST - Java

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

Kth Smallest Element in a BST - LeetCode

---

문제

Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.

 

Example 1:

Input: root = [3,1,4,null,2], k = 1
Output: 1

Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3

 

Constraints:

• The number of nodes in the tree is n.
• 1 <= k <= n <= 104
• 0 <= Node.val <= 104

 

Follow up: If the BST is modified often (i.e., we can do insert and delete operations) and you need to find the kth smallest frequently, how would you optimize?

---

풀이

풀이 과정

이진 탐색 트리 root와 정수 k가 주어졌을 때, 트리의 모든 노드 값 중 k번째로 작은 값을 찾는 문제이다.

트리를 순회하는 방법에는 크게 3가지가 있으며 간단하게 각 순회의 탐색 순서는 다음과 같다.

1. 전위 순회 (Preorder Traversal) : root 노드 → 왼쪽 노드 → 오른쪽 노드
2. 중위 순회 (Inorder Traversal) : 왼쪽 노드 → root 노드 → 오른쪽 노드
3. 후위 순회 (Postorder Traversal) : 왼쪽 노드 → 오른쪽 노드 → root 노드

이진 탐색 트리의 특징은 왼쪽 노드의 값은 root 노드보다 작고, 오른쪽 노드의 값은 root 노드보다 큰 값으로 구성 되어 있기 때문에 (왼쪽 → root → 오른쪽) 순서대로 오름차순 정렬되어 있다고 볼 수 있다.

이번 문제에서는 제일 작은 수부터 차례대로 탐색해 k번째 노드를 찾아야 하므로 정렬된 순서대로 탐색이 가능한 중위 순회를 이용하여 풀이한다.

현재 탐색중인 노드가 몇 번째로 작은 숫자인지 저장할 변수와 정답을 저장할 변수 하나를 선언한다.

int count = 0;
int answer = 0;

 

다음으로 트리를 중위 순회하기위한 함수를 생성한다.
왼쪽 노드부터 재귀적으로 호출하여 가장 작은 값부터 탐색을 시작하고 현재 탐색중인 노드의 카운트와 k가 같다면 정답 변수에 현재 노드 값을 저장하고 탐색을 종료한다. 현재 카운트가 k와 같지 않은 경우 오른쪽 노드를 탐색한다.
만약 현재 노드가 null인 경우 탐색을 종료한다.

// 중위 순회
public void inorderTraversal(TreeNode node, int k){
    // 노드가 없다면 탐색 종료
    if(node == null) return;

    // 왼쪽 노드 탐색
    inorderTraversal(node.left, k);
    // 카운트를 증가시키고 그 값이 k와 같다면 현재 노드의 값을 정답으로 저장하고 탐색 종료
    if(++count == k) {
        answer = node.val;
        return;
    }
    // 오른쪽 노드 탐색
    inorderTraversal(node.right, k);
}

 

생성한 함수를 호출하여 결과값을 return한다.

 public int kthSmallest(TreeNode root, int k) {
    inorderTraversal(root, k);

    return answer;
}

---

최종 코드

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    // 몇 번째로 작은 숫자인지 카운트를 저장할 변수
    int count = 0;
    int answer = 0;
    public int kthSmallest(TreeNode root, int k) {
        inorderTraversal(root, k);

        return answer;
    }

    // 중위 순회
    public void inorderTraversal(TreeNode node, int k){
        // 노드가 없다면 탐색 종료
        if(node == null) return;

        // 왼쪽 노드 탐색
        inorderTraversal(node.left, k);
        // 카운트를 증가시키고 그 값이 k와 같다면 현재 노드의 값을 정답으로 저장하고 탐색 종료
        if(++count == k) {
            answer = node.val;
            return;
        }
        // 오른쪽 노드 탐색
        inorderTraversal(node.right, k);
    }
}

---