本文主要是介绍leetcode 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);}};
这篇关于leetcode 230. 二叉搜索树中第K小的元素 medium的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
