刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/kth-smallest-element-in-a-bst/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给定一个二叉搜索树的根节点 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

提示：

• 树中的节点数为 n 。
• 1 <= k <= n <= 10^4
• 0 <= Node.val <= 10^4

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

思路

首先明确二叉搜索树性质

二叉搜索树性质

• 根结点的值大于所有左子树中节点的值
• 根结点的值小于所有右子树中节点的值

所以其实找第k小的值，也就是在二叉树的中序遍历结果中找第k小的元素。

优化

所谓优化，无非时间复杂度和空间复杂度。
而对应优化的方向有两个：

• 不完全遍历完就可以出结果
• 不存储遍历结果，只取关心的结果

而我们在遍历时其实本身就能够感知到遍历到的是第几个数，因此只需要维护一个计数值，到第K个数时中断遍历，返回当前的值即可

至此，细节详见代码注释

代码

func kthSmallest(root *TreeNode, k int) int {
	res := 0
	var dfs func(root *TreeNode)
	dfs = func(root *TreeNode) {
        // 中序遍历, 遍历左子树
		if root.Left != nil {
			dfs(root.Left)
		}
        // 中序遍历, 遍历完左子树后遍历根节点
		k--
        // 减为0说明找到了第K个值，赋值返回
		if k == 0 {
			res = root.Val
			return
		}
        // 中序遍历, 遍历右子树
		if root.Right != nil {
			dfs(root.Right)
		}
	}
	dfs(root)
	return res
}