LeetCode 솔루션 분류

230. Kth Smallest Element in a BST

컨텐츠 정보

본문

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

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


[Medium] 230Kth 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?

관련자료

댓글 3

mingki님의 댓글

  • 익명
  • 작성일
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;
    }
};

9dea0936님의 댓글

  • 익명
  • 작성일
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

bobkim님의 댓글

  • 익명
  • 작성일
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;
    }
};
LeetCode 솔루션 357 / 1 페이지
번호
제목
이름

최근글


인기글


새댓글


Stats


  • 현재 접속자 745 명
  • 오늘 방문자 5,061 명
  • 어제 방문자 6,932 명
  • 최대 방문자 14,831 명
  • 전체 회원수 1,481 명
알림 0