.png&blockId=5f7573ad-6867-4d59-999e-722aced04aeb)
Medium
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
Plain Text
복사
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
Output: 3
Plain Text
복사
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?
My solution
트리로 이루어진 트리노드가 입력으로 들어오는 문제이다. jest로 돌리기 번거로운 문제다.
문제 설명에 1-indexed라는 단어가 있는데 무슨 의미인지 모르겠다 구글링해보면 indexed tree가 나오는데 블로그 설명에 의하면
인덱스 트리는 웬만하면 Full Binary Tree로 구성하는게 좋습니다!
트리에 null이 들어오는 이 문제에는 해당이 되지 않는 것 같다.
어떤 내용에 대해 빨리 찾아보기 위해 먼저 보는 것
어떤 내용에 대해 빨리 찾아보기 위해 먼저 보는 것의 1로 인덱스되었다는 것은 k번째 수가 여러개일 때 가장 첫번째로 만나는 수를 뜻할 것이라고 생각했다.
왜냐하면 is uniques라는 조건이 없기 때문이다.
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?
덧붙여서(후속작업) : BST가 자주 수정되거나 K번째 작은 수를 빈번하게 찾아야만 한다면, 어떻게 최적화할 것인가?
⇒ 이에 대해 생각나지 않는 걸 보니 트리에 대해 많이 공부해야 될 것 같다.
먼저 트리 공부 :
우선 bst의 TC 예시를 보면 일반적인 bst의 삽입연산으로 만들어진 것을 추측할 수 있다.
50, 15, 62, 80, 7, 54, 11
그리고 잊고 있던 걸 하나 알게 되었는데, 아래와 같이 순회하는 방식으로 정렬도 가능한 게 bst의 특징이다.
이진 탐색 트리의 특징
1. BST의 Inorder Traversal을 수행하여 모든 키를 정렬된 순서로 가져올 수 있습니다.
위 트리에 inorder traversal 결과는 다음과 같습니다.
7, 11, 15, 50, 54, 62, 80
시간 복잡도는 아래와 같이 달라진다고 한다.
2. BST의 검색에 대한 시간복잡도는 균형 상태이면 O(logN)의 시간이 걸리고 불균형 상태라면 최대 O(N) 시간이 걸립니다. skewed bst면 O(N)이 걸린다는 것이다. (배열이랑 다를 바 없는 상태, 트리 쓰는 이유는 균형 잡힌 트리를 사용해서 O(logN)인 검색을 수행하고 싶어서이다.)
+ 트리를 왜 사용하나?
Tree 를 사용하는 이유
•
탐색, 삽입, 삭제가 빠르다
•
정렬 된 배열에서는 삽입, 삭제 작업이 비효율적이다
•
링크드 리스트는 검색이 느리다
•
평균적으로 O(log n) 의 시간복잡도를 가진다
또한, 문제 설명에 uniques라는 언급이 없었는데 bst는 중복이 없어야 되는 게 기본 특징이라고 한다.
중복을 허용하는 이진탐색트리를 만들 필요가 있을까? 합당한 이유가 있다면 굳이 중복된 노드를 트리에 삽입하는 것 보다는 노드에 count 값을 가지게 하는 것으로 처리하는 게 효율적이라고 생각한다.
개인적인 생각으로 이진탐색트리가 필수적으로 중복이 없어야 하는 자료구조는 아닌 것 같다. 다만 중복이 없어야 검색의 효율을 높일 수 있을 뿐
우선은 inorder traversal 방식으로 순회하면 노드가 오름차순으로 정렬되어 방문하게 된다는 사실을 알 수 있었고 vscode에서 돌려보는 것은 굉장히 불편해서 아래와 같이 콘솔을 찍어보았는데 정말 오름차순으로 출력해주었다.
자 이렇게 되면 몇번째로 작은 수를 구하는 것이 굉장히 쉬워진다.
방문할 때마다 cnt를 센다. 원하는 K가 되었을 때 해당 노드의 값을 출력해보자.
일단 jest로 돌려보고 싶어서 트리 만드는 것까지 같이 넣었는데 문제는 배열로 입력을 주기 때문에 null도 넣는다는 것이다. 우리는 귀찮기 때문에 null을 없애주는 대신 로직에 null인 경우는 노드를 삽입하지 않도록 insertNode 함수를 조금 수정해보려고 한다.
val이 null로 들어오면 그냥 node를 다시 리턴해버리는 것이다. 그럼 null 값이 들어왔을 때 this.root도 같이 주어졌을텐데 이 this.root가 다시 this.root에 재할당되므로 변화가 없다.
function Node(val) {
this.val = val === undefined ? 0 : val;
this.left = this.left === undefined ? null : this.left;
this.right = this.right === undefined ? null : this.right;
}
function BinaryTree() {
this.root = null;
}
BinaryTree.prototype._insertNode = function (node, val) {
// leetCode input [1, null, 3] <- remove null-val node
if (val === null) return node;
// ESLint) Assignment to function parameter 'node' <- node = new Node(val);
if (node === null) {
const newNode = new Node(val);
return newNode;
}
if (val < node.val) {
node.left = this._insertNode(node.left, val);
} else if (val > node.val) {
node.right = this._insertNode(node.right, val);
}
return node;
};
BinaryTree.prototype.insert = function (val) {
this.root = this._insertNode(this.root, val);
};
JavaScript
복사
콘솔을 찍어보니 k가 undefined로 나왔다.
count는 1씩 오르고 있다.
k를 매개변수에서 받아주고 있지 않아서다.
이걸 고치고 나니까 count가 제대로 안 오르는 걸 볼 수 있었다. 생각해보면 count라는 애를 함수에서 내려줄 필요 없이 inOrder라는 함수가 정의된 스코프에서 공유하게끔 즉시실행함수로 감싸서 클로저를 만들면 되겠다는 생각이 들었다. 한번 시도해보았다.
const inOrder = (function () {
let count = 0;
function inOrderTraverse(focusNode, k) {
if (focusNode != null) {
count++;
inOrderTraverse(focusNode.left, count, k);
console.log(focusNode, focusNode.val + ' ', count, k);
if (count === k) {
console.log(focusNode.val, count, k);
return focusNode.val;
}
inOrderTraverse(focusNode.right, count, k);
}
}
return function (root, count, k) {
return inOrderTraverse(root, count, k);
};
})();
JavaScript
복사
즉시실행함수에 인자나 인수를 전달하지 않았다. return 에 inOrderTraversal 함수를 명시해주어서 여기서 매개변수를 받도록 했다. return 문 이전엔 스코프로 묶어주게끔 지역변수 count와 inOrder~ 함수의 정의를 작성했다. 콘솔을 출력해보면
2 1
3 2
const inOrder = (function () {
let count = 0;
function inOrderTraverse(focusNode, k) {
if (focusNode != null) {
count++;
inOrderTraverse(focusNode.left, count, k);
JavaScript
복사
count++문이 실행되는 시점은 저기가 아니라 레벨 오더의 출력시점에 같이 실행되어야 한다.
그래서 inOrder에서 노드를 출력할 때 count를 한번씩 증가시켜서 k가 되었을 때 answer에 저장하게 했다.
이렇게 제출을 하니 클로저에 있는 count와 answer가 다시 함수를 호출할 때도 동일한 렉시컬 스코프를 가지고 있어서 count===k가 잡히지 않았다. (inOrderTraverse라는 함수 정의는 즉시실행함수 안에서 한번만 이루어지므로 계속해서 동일한 렉시컬스코프다. 단지 kthSmallest라는 함수만 여러번 호출해서 테스트케이스를 검사하는 것이기 때문이다.)
따라서 렉시컬 스코프 내에서 return 으로 function을 실행할 때마다 새롭게 count, answer를 초기화해주어야지 count===k라는 조건을 검사할 수 있었다.
그리고 이건 어마어마하게 느린 성능을 보여줬다. 표 안에 포함되지도 않았다.
트리를 만드는 코드도 포함했고, 콘솔 출력하는 문도 있었기 때문인 것 같아서 전부 지우고 33%보다는 빠른 성능을 확인했다.
소스코드
const inOrder = (function () {
let count = 0;
let answer = -1;
function inOrderTraverse(focusNode, k) {
if (focusNode != null) {
inOrderTraverse(focusNode.left, k);
count++;
if (count === k) answer = focusNode.val;
// console.log(count === k, '#', focusNode.val);
inOrderTraverse(focusNode.right, k);
}
}
return function (root, k) {
count = 0;
answer = -1;
inOrderTraverse(root, k);
return answer;
};
})();
/**
* Definition for a binary tree node.
* function TreeNode(val, left, right) {
* this.val = (val===undefined ? 0 : val)
* this.left = (left===undefined ? null : left)
* this.right = (right===undefined ? null : right)
* }
*/
/**
* @param {TreeNode} root
* @param {number} k
* @return {number}
*/
const kthSmallest = function (root, k) {
return inOrder(root, k);
};
test('TC1', () => {
expect(kthSmallest([3, 1, 4, null, 2], 1)).toStrictEqual(1);
});
// test('TC2', () => {
// expect(kthSmallest([5, 3, 6, 2, 4, null, null, 1], 3)).toStrictEqual(3);
// });
JavaScript
복사
