Skip to content

LeetCode: 230-Kth Smallest Element in a BST 解題紀錄

Last Updated on 2022-04-18 by Clay

題目

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?

題目給定一組二元搜索樹和 k 值。我們要返回的，就是第 k 小的節點值。

解題思路

今天下班回家後太累了，follow up 看起來有點小麻煩就跳過不去理解它了。


深度優先搜索（DFS）解法

使用 DFS 解題的話，按照左節點展開 > 當前節點值 > 右節點展開…… 這樣的順序依序去讀值，然後每次拿到新的節點值時判斷是否計數已經來到了 k，在計數等於 k 時一路返回到最外頭，就能剛好把第 k 小的節點值當作答案。


深度優先搜索（DFS）解法複雜度

在 k 等於節點數的情況下我們得遍歷整棵 BST，故時間複雜度應設定為 O(n)。

而我們可以只宣告一些整數變數來完成這題，所以空間複雜度可以想像成 O(1)。

Time complexityO(n)
Space complexityO(1)


深度優先搜索（DFS）解法 C++ 範例程式碼

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    void dfs(TreeNode* root, int& n, int& k) {
        // Base case
        if (root == nullptr) return;
        
        // Left
        if (root->left != nullptr) {
            dfs(root->left, n, k);
        }
        if (k == 0) return;
        
        // Current node
        n = root->val;
        --k;
        if (k == 0) return;
        
        // Right
        if (root->right != nullptr) {
            dfs(root->right, n, k);
        }
        if (k == 0) return;
    }
    
    int kthSmallest(TreeNode* root, int k) {
        // Init
        int n;
        
        // DFS
        dfs(root, n, k);
        
        return n;
    }
};



深度優先搜索（DFS）解法 Python 範例程式碼

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
        # Init
        n = 0
        
        def dfs(root):
            nonlocal n, k
            
            # Base case
            if root:
                # Left
                if root.left:
                    dfs(root.left)

                if k == 0: return

                # Current node
                n = root.val
                k -= 1
                if k == 0: return

                # Right
                if root.right:
                    dfs(root.right)

                if k == 0: return

        # DFS
        dfs(root)
        
        return n

References

Read More

Tags:

Leave a Reply