leetcode 230. 二叉搜索树中第K小的元素 mediumleetcode 230. 二叉搜索树中第K小的元素 medium 题目描述：

62 阅读 0 评论 41 点赞

我是靠谱客的博主如意小伙，最近开发中收集的这篇文章主要介绍leetcode 230. 二叉搜索树中第K小的元素 mediumleetcode 230. 二叉搜索树中第K小的元素 medium 题目描述：，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

leetcode 230. 二叉搜索树中第K小的元素 medium

题目描述：

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

解题思路：

普通解法： bst的中序（左中右）是一个递增序列，所以只要中序遍历，并且计数，到第k个，输出就objk了。

进阶问题：只要修改原树结点的结构，使其保存包括当前结点和其左右子树所有结点的个数，这样我们就可以用递归的方法快速定位到第k小的节点了。

具体的方法是：

如果当前节点的左子树节点数大于等于k，去左子树找第k个

如果左子树的节点数等于k-1，返回当前节点

如果左子树的节点数a小于k-1，去右子树找它的第 k-（a+1）个节点。

代码：

普通解法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(root ==nullptr)
            return -1;
        stack<TreeNode *> sta;
        TreeNode *cur=root;
        while(cur || sta.size()){
            while(cur){
                sta.push(cur);
                cur=cur->left;
            }
            
            if(!sta.empty()){
                cur=sta.top();
                sta.pop();
                --k;
                if(k==0) return cur->val;
                cur=cur->right;
                
            }
        }
        
        return -1;
    }
};

递归解法：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int kthSmallest(TreeNode* root, int k) {
        if(!root)
            return -1;
        int a=size(root->left);
        if(a>=k) return kthSmallest(root->left,k);
        else if(a==k-1) return root->val;
        else return kthSmallest(root->right,k-(a+1));
    }
    
    
    int size(TreeNode *root){
        if(!root)
            return 0;
        return 1+size(root->left)+size(root->right);
    }
    
};