LeetCode 솔루션

230. Kth Smallest Element in a BST

mingki 쪽지보내기 메일보내기 자기소개 아이디로 검색 전체게시물 작성
작성일 2022.04.18 14:50

6,892 조회
3 댓글
0 추천
0 비추천
목록

글검색

게시글 쓰기

[ LeetCode 시즌 3 ] 2022년 4월 17일 문제입니다

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

[Medium] 230. Kth Smallest Element in a BST

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?

#leetcode, #문제풀이, #시즌3, #medium, #Amazon, #Uber, #Facebook, #Tree, #Depth-Frist Search(DFS), #Binary Search Tree(BST), #Binary Tree

링크

https://leetcode.com/problems/kth-smallest-element-in-a-bst/ 2505 회 연결

익명
작성일 2022.04.18 15:02

C++
Runtime: 30 ms, faster than 29.91% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.1 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.

class Solution {
    int res = 0;
    int curr = 0;
    
private:
    void helper(TreeNode *root, int k) {
        if (root) {
            helper(root->left, k);
            res = ++curr == k ? root->val : res;
            helper(root->right, k);
        }
    }
    
public:
    int kthSmallest(TreeNode* root, int k) {
        helper(root, k);
        return res;
    }
};

익명
작성일 2022.04.18 19:21

class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        head = root
        self.ans = 0
        self.idx = 0
        def quickSearch(node):
            if not node:
                return 
            
            quickSearch(node.left)
            self.idx += 1
            if self.idx == k:
                self.ans = node.val
            quickSearch(node.right)
        
        quickSearch(head)
        return self.ans

익명
작성일 2022.04.18 21:49

Runtime: 27 ms, faster than 41.30% of C++ online submissions for Kth Smallest Element in a BST.
Memory Usage: 24.2 MB, less than 61.00% of C++ online submissions for Kth Smallest Element in a BST.

class Solution {
public:
    int counter=0;
    int knum;
    TreeNode* p_ans;
    void findKth(TreeNode* &root){
        
        if(root->left != nullptr){
            findKth(root->left);
        }
        
        counter++;
        if(counter == knum){
            p_ans=root;
            return;
        }

        if(root->right != nullptr){
            findKth(root->right);
        }
        return ;
    };
    
    int kthSmallest(TreeNode* root, int k) {
        knum=k;
        findKth(root);
        return p_ans->val;
    }
};