LeetCode 230 - Kth Smallest Element in a BST

Kth Smallest Element in a BST - LeetCode

 

이진 탐색 트리의 root가 주어졌을 때, k번째로 작은 값을 반환하라.

 

예를 들어 트리가 [3, 1, 4, null, 2]이고 k = 1이라면 가장 작은 값이니 1이 정답이 된다.

다음으로 [5, 3, 6, 2, 4, null, null, 1] 이고 k = 3이면 1, 2, 3으로 3이 정답이 된다.

주어진 자료구조가 BST(이진 탐색 트리)인 점을 주목해야한다.

이진 탐색 트리는 중위순회를 했을 시 데이터가 정렬된 채로 반환이 된다.

그렇다면 중위순회를 통해 정렬된 1차원 데이터를 얻고 거기서 k번 째 값을 반환하면 될 것이다.

1. 중위순회를 통해 List <Integer>를 구성한다.
2. 해당 List에서 k번째 값을 반환한다.

/**
 * 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 {
    public int kthSmallest(TreeNode root, int k) {
        List<Integer> numbers = new ArrayList<>();
        inOrder(root, numbers);
        return numbers.get(k - 1);
    }
    
    private void inOrder(TreeNode node, List<Integer> numbers) {
        if (node == null) {
            return;
        }

        inOrder(node.left, numbers);
        numbers.add(node.val);
        inOrder(node.right, numbers);
    }
}

굳이 전체를 순회하지 않더라도 k개만 순회하고 k개에 도달하면 순회를 그만둬도 될 것 같다.