题目大意：
二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
输入: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 输出: 1
示例 2:
输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
输出: 3进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=230
解题思路分析：
看到BST二叉搜索树的题目，我们要想到题目多数情况下是在考察二分查找的逻辑。也就是说我们算法的时间复杂度尽量要压缩在logn级别才可以。对于本题我们需要使用二分查找的方式，找到第k小的元素在哪里，我们可以将所有数字分为三个部分：左子树，当前节点，右子树。根据BST的特性可得出，左子树中所有节点一定小于当前节点，当前节点一定小于右子树中所有节点，因此我们只要知道三个部分的节点个数，那么我们就可以很容易的判断出k在哪个部分之中，如果k在中间部分（当前节点）的话，那么当前节点即是返回值。除此之外，将问题递归至子问题即可。
具体解题思路：
- 将当前节点分为3个部分：左子树，当前节点，右子树。
- 要寻找第k小的节点，那么我们先查看左子树中的节点数leftCount，如果leftCount大于等于k，说明第k小的元素在左子树中，我们递归至左子树。反之如果左子树中节点数leftCount小于k，那么说明第k小的数字不在左子树，这时将k减去leftCount。
- 接下来查看当前节点，如果此时k等于1，那么说明结果一定是当前节点，话句话说，除了左子树中的数字之外，当前节点的数字一定是最小的。（左子树的节点个数已在上一步骤中消耗掉）反之，如果k大于1，那么我们将k减去1。
- 最后再查看右子树，此时的k值与最初时相比已经发生两次变化 k1=k-leftCount-1; 我们将此时的k值称之为k1，目前为止，我们已知第k小的元素一定存在于右子树中，实际上也就是求右子树中第k1小的元素（递归至右子树）。
- 求某个节点下总节点数的方法也不难，只要dfs递归一下所有节点即可，具体实现可参照代码。
实现代码：
public int kthSmallest(TreeNode root, int k) {
if(root.left!=null){ // 左子节点不为空
// 统计左子树节点个数
int leftCount=count(root.left);
if(k<=leftCount){ // 如果节点个数大于等于k
// 说明第k小的元素在左子树中，递归至左子树
return kthSmallest(root.left, k);
}else{
// 反之将k减去左子树节点个数
k-=leftCount;
}
}
// 如果k等于1，当前节点即是返回结果
if(k==1) return root.val;
// 反之将k减去1
else k-=1;
// 这时第k小元素一定在右子树，递归至右子树
return kthSmallest(root.right, k);
}
// 统计root节点下节点个数
int count(TreeNode root){
int res=1; // 当前节点个数
if(root.left!=null) // 累加左子树节点个数
res+=count(root.left);
if(root.right!=null) // 累加右子树节点个数
res+=count(root.right);
return res;
}本题解法执行时间为0ms。
Runtime: 0 ms, faster than 100.00% of Java online submissions for Kth Smallest Element in a BST.
Memory Usage: 39.4 MB, less than 11.93% of Java online submissions for Kth Smallest Element in a BST.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-230-kth-smallest-element-in-a-bst-解题思路分析/