10.二叉搜索树中第k小的元素（medium）

1.题目链接：

230. 二叉搜索树中第 K 小的元素 - 力扣（LeetCode）230. 二叉搜索树中第 K 小的元素 - 给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 小的元素（从 1 开始计数）。 示例 1：[https://assets.leetcode.com/uploads/2021/01/28/kthtree1.jpg]输入：root = [3,1,4,null,2], k = 1输出：1示例 2：[https://assets.leetcode.com/uploads/2021/01/28/kthtree2.jpg]输入：root = [5,3,6,2,4,null,null,1], k = 3输出：3  提示： * 树中的节点数为 n 。 * 1 <= k <= n <= 104 * 0 <= Node.val <= 104 进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化算法？https://leetcode.cn/problems/kth-smallest-element-in-a-bst/description/2.题目描述：

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素

（从 1 开始计数）。​

示例 1：​

           输入：root = [3,1,4,null,2], k = 1​
           输出：1​
示例 2：​

输入：root = [5,3,6,2,4,null,null,1], k = 3​
输出：3​

3. 解法二（中序遍历 + 计数器剪枝）：​
算法思路：
上述解法不仅使用大量额外空间存储数据，并且会将所有的结点都遍历一遍。

但是，我们可以根据中序遍历的过程，只需扫描前 k 个结点即可。​
因此，我们可以创建一个全局的计数器 count，将其初始化为 k，每遍历一个节点就将 count--。直到某次递归的时候，count 的值等于 1，说明此时的结点就是我们要找的结果。​

算法流程：
1. 定义一个全局的变量 count，在主函数中初始化为 k 的值（不用全局也可以，当成参数传入递归过程中）；
递归函数的设计：int dfs(TreeNode* root)：​
•返回值为第 k 个结点；​

递归函数流程（中序遍历）：
1. 递归出口：空节点直接返回 -1，说明没有找到；​
2. 去左子树上查找结果，记为 retleft：​
         a. 如果 retleft == -1，说明没找到，继续执行下面逻辑；​
         b. 如果 retleft != -1，说明找到了，直接返回结果，无需执行下面代码（剪枝）；

​3. 如果左子树没找到，判断当前结点是否符合：
         a. 如果符合，直接返回结果
4. 如果当前结点不符合，去右子树上寻找结果。

Java算法代码：

class Solution {int count;int ret;public int kthSmallest(TreeNode root, int k) {count =k;dfs(root);return ret;}void dfs(TreeNode root){if(root == null || count ==0) return ;dfs(root.left);count--;if(count == 0 ) ret = root.val;if(count == 0) return;dfs(root.right);}
}

执行结果：

递归展开：这里有一个细节，按照笔者这里的展开，实际上是没有进行我们预期的那种减枝（读者可以仔细阅读）--- 在dfs左子树之后去添加if（count == 0）return；也可以进行减枝，本题中多次进行减枝，请好好体会。

逻辑展开：

这道题目，建议好好的研究一下怎么去减枝，这道题不能想到中序遍历。解决方法容易想到，但是这里减枝，你得自己手动画画，才能更好的理解。

---------------------------------------------------------------------------------------------------------------------------------

记住，相信你的递归函数，它可以做到！

记住，不理解时候，去尝试手动展开！

记住，逻辑展开（你不可能对所有的题目都进行手动展开）！