1，问题简述
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
2，示例
代码语言：javascript复制示例 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
输出: 33，题解思路
使用二叉树的中序遍历方式进行解决
4，题解程序
代码语言：javascript复制
import java.util.ArrayList;
import java.util.List;
public class KthSmallestTest3 {
public static void main(String[] args) {
TreeNode t1 = new TreeNode(3);
TreeNode t2 = new TreeNode(1);
TreeNode t3 = new TreeNode(4);
TreeNode t4 = new TreeNode(2);
t1.left = t2;
t1.right = t3;
t2.right = t4;
int k = 1;
int kthSmallest = kthSmallest(t1, k);
System.out.println("kthSmallest = " kthSmallest);
}
private static List<Integer> list = new ArrayList<>();
public static int kthSmallest(TreeNode root, int k) {
if (root == null) {
return 0;
}
dfs(root);
return list.get(k - 1);
}
private static void dfs(TreeNode root) {
if (root == null) {
return;
}
if (root.left != null) {
dfs(root.left);
}
list.add(root.val);
if (root.right != null) {
dfs(root.right);
}
}
}
5，题解程序图片版
6，总结一下
这个题目前值写了一种方式进行解决，也可以基于队列的方式进行求解，不过消耗时间和空间复杂度也比较高，这里没有给出具体的程序，这里基于递归的方式进行解决，利用系统栈的特点来解决，也是比较快速的，后面有时间在来看看利用队列的方式来一段示例程序
