每天做一道算法题，循序渐进，按算法分类刷题。坚持下去，看能坚持多久，也看最终能有多大成效。
二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
示例 1:
<code>输入: root = [3,1,4,null,2], k = 1
3
/ \\
1 4
\\
2
输出: 1/<code>
示例 2:
<code>输入: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \\
3 6
/ \\
2 4
/
1
输出: 3/<code>
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？
解决方案
方案1：从根节点开始，获取左边节点的数目和k进行比较，如果大于k，则说明第k小的节点在左子树，就递归在左子树查找，如果小于k，则说明第k小的节点在右子树，就递归在右子树查找。如果相等说明找到对应节点。
方案2：中序遍历树节点存放在列表中，树节点是从小到大排列，然后直接循环列表就可以找到对应节点。
递归实现方案
中序遍历实现方案
分享到:
閱讀更多 突破程序員 的文章
