LeetCode 230번: Kth Smallest Element in a BST(JAVA)
문제출처 230번: Kth Smallest Element in a BST
❔ 문제
BST의 root 노드가 주어졌을 때, 이 트리의 k번째 작은 값을 출력.
⏩ 예시
Input: root = [5,3,6,2,4,null,null,1], k = 3 Output: 3
❕ 문제풀이
/**
* 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;
public int kthSmallest(TreeNode root, int k) {
count = k; // 1.
return inorder(root);
}
public int inorder(TreeNode node){
if(node == null) return -1; // 2.
int result = -1;
result = inorder(node.left); // 3
if(result != -1) return result; // 3.
count--; // 4.
if(count == 0) return node.val; // 5.
return inorder(node.right); // 6.
}
}
- k번째 작은 값을 찾기 위한 카운팅 인스턴수 변수를 초기화한다.
- 해당 노드가 null 이면 탐색이 더이상 불가하므로 -1을 반환한다.
- 중위 순회할 것이므로 왼쪽 노드부터 탐색한다. 만약 -1값이 아닌 값이 반환될 경우 그 값을 return 한다.
- 중위 순회 도중 만난 값은 최소값의 순서가 되므로 카운팅을 줄인다.
- 만약 카운트가 0이라면 k번째 작은 값이 되므로 해당 값을 return 한다.
- 중위 순회의 오른쪽 노드를 탐색하여 나온 값을 return 한다.
💯 고찰
BST를 DFS방식으로 순회하는 방법을 택하였다. 그 중에서도 최소값을 찾기 위해선 중위 순회를 해야한다고 판단하여 Solution에 이르렀다.
다른 여러 풀이도 결국 중위 순회 방식으로 O(N) 시간에 해결하고 있었다. 다만 DFS의 중단지점 설정이 각 코드마다 달랐었다. 나의 경우에는 return 값으로 판별했지만 인스턴스 변수나 클래스 변수를 별도로 두어 결과가 도출되었을 경우 return 해버리는 코드들이 많았다.
