참고
문제해설
NOTE
•
입력 값 ⇒ TreeNode와 k 정수
•
출력 값 ⇒ k번째로 작은 정수 값을 찾는다!
•
후속 조치 ⇒ BST가 자주 수정되는 경우에 어떻게 최적화할 수 있는가?
문제 로직고민
NOTE
•
이전 문제에서 중위순회가 트리의 요소를 오름차순하는걸 알았으므로 그걸 응용해서 진행한다!
◦
로직은 괜찮은거 같은데 후속 조치 부분이 만족되는지 잘 모르겠다.
◦
자주 수정된다는 의미는 크기가 자주 변경된다는 의미이다.
◦
현재 로직대로라면 Tree의 node개수만큼 탐색해야 하기 때문에 만약 크기가 많아지는 시나리오에서 문제가 있을것 같으므로 k에 도달하면 재귀를 멈추는 로직을 추가한다.
작성코드
NOTE
class Solution {
int cnt = 1;
int result = 0;
public int kthSmallest(TreeNode root, int k) {
inOrder(root, k);
return result;
}
public void inOrder(TreeNode node, int k){
if(node == null) return;
inOrder(node.left, k);
if(cnt == k) result = node.val;
else if(cnt > k) return;
cnt++;
inOrder(node.right, k);
}
}
Java
복사
정답코드
NOTE
class Solution {
public int kthSmallest(TreeNode root, int k) {
int[] ind = {0,0};
buildList(root, ind, k);
System.gc();
return ind[1];
}
public void buildList(TreeNode node, int[] ind, int k){
if (node == null){
return;
}
buildList(node.left, ind, k);
ind[0]++;
if(ind[0] == k){
ind[1] = node.val;
}
buildList(node.right, ind, k);
}
}
Java
복사
메모리를 가장 적게 사용하는 코드
•
동일한 로직을 사용하고 Memory가 2MB밖에 차이안나므로 참고만 하고 넘어간다.