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

题目描述：

给定一个二叉搜索树的根节点 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 个节点时，就返回这个节点的值。

func kthSmallest(root *TreeNode, k int) int {
	var stack = make([]*TreeNode, 0)
	stack = append(stack, root)
	for root != nil || len(stack) != 0 {
		for root != nil {
			stack = append(stack, root)
			root = root.Left
		}
		root = stack[len(stack)-1]
		stack = stack[:len(stack)-1]
		k--
		if k == 0 {
			return root.Val
		}
		root = root.Right
	}
	return 0
}

复杂度：

• 时间复杂度：O(N)，其中 N 是树中的节点个数.
• 空间复杂度：O(1)，只使用常数额外空间。

执行结果：

• 执行耗时:6 ms,击败了75.69% 的Go用户
• 内存消耗:6 MB,击败了64.67% 的Go用户