跳转至

230 二叉搜索树第k小的元素

中序遍历(直接版)

/**
 * 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 {
private:
    vector<int> ans;
    void inOrder(TreeNode* root){
        if(!root)
            return;
        inOrder(root->left);
        ans.push_back(root->val);
        inOrder(root->right);
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        inOrder(root); 
        return ans[k - 1];
    }
};

中序遍历(优化版)

所谓优化就是不需要遍历整棵树,遍历过程中找到对应的节点就可以返回

递归

感觉用递归不太适合,这里就不贴出来了

迭代

/**
 * 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:
    int kthSmallest(TreeNode* root, int k) {
        stack<TreeNode*> stk;
        TreeNode* cur = root;
        while(cur || !stk.empty()){
            if(cur){
                stk.push(cur);
                cur = cur->left;
            }else{
                cur = stk.top();
                stk.pop();
                // 从k - 1开始计数
                k--;
                // 因此k == 0时对应第k个小的值
                if(k == 0)
                    return cur->val;
                cur = cur->right;
            }
        }
        return 0;
    }
};

复杂度分析

时间复杂度:O(H+k),其中 H 是树的高度。在开始遍历之前,我们需要 O(H) 到达叶结点。当树是平衡树时,时间复杂度取得最小值 O(logN+k);当树是线性树(树中每个结点都只有一个子结点或没有子结点)时,时间复杂度取得最大值 O(N+k)。

空间复杂度:O(H),栈中最多需要存储 H 个元素。当树是平衡树时,空间复杂度取得最小值 O(logN);当树是线性树时,空间复杂度取得最大值 O(N)

方法二:记录子树的结点数

如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化算法?

详见题解:

https://leetcode.cn/problems/kth-smallest-element-in-a-bst/solutions/1050055/er-cha-sou-suo-shu-zhong-di-kxiao-de-yua-8o07/?envType=study-plan-v2&envId=top-100-liked

/**
 * 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 {
private:
    unordered_map<TreeNode*,int> nodeNum;
    int setNodeNum(TreeNode* node){
        if(!node)
            return 0;
        int leftNum = setNodeNum(node->left);
        int rightNum = setNodeNum(node->right);
        nodeNum[node] = leftNum + rightNum + 1;
        return nodeNum[node];
    }
    int getNodeNum(TreeNode* node){
        if(node && nodeNum.count(node))
            return nodeNum[node];
        else
            return 0;
    }
public:
    int kthSmallest(TreeNode* root, int k) {
        if(!root)
            return 0;
        setNodeNum(root);
        TreeNode* node = root;
        while(node){
            int leftNum = getNodeNum(node->left);
            // 如果左子树节点树比 k - 1小,说明第k个数在右子树
            // 此时左子树有 leftNum 个节点
            // 也就是说此时我们已经找到了第k个节点左边的leftNum个节点
            // 我们还需要填充k - 1 - leftNum个节点,就可以找到第k个节点
            // 因此k = k - 1 - leftNum
            if(leftNum < k - 1){
                node = node->right;
                k -= leftNum + 1;
            }else if (leftNum == k - 1){
                return node->val;
            }else{
                node = node->left;
            }
        }
        return 0;
    }
};

下一次寻找第k小的节点,只需要查找哈希表即可,为\(O(1)\)时间复杂度