题目描述：
给定一个二叉搜索树的根节点 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
代码思路：
* 方法通过先将树的所有节点值放入一个列表，排序后返回第k个元素。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {public int kthSmallest(TreeNode root, int k) {List<Integer> list = new ArrayList();addlist(root,list);Collections.sort(list);return list.get(k-1);}public void addlist(TreeNode root, List<Integer> list){if(root==null){return;}list.add(root.val);addlist(root.left,list);addlist(root.right,list);}
}时间复杂度：
- 遍历树：遍历二叉树的所有节点，时间复杂度是O(n)，其中n是树中节点的数量。
- 排序：对节点值进行排序，时间复杂度是O(n log n)。
- 因此，整体时间复杂度是O(n log n)，其中n是树中节点的数量。
空间复杂度：
- 我们使用了一个
list来保存树中的所有节点值，因此空间复杂度是O(n)，其中n是树中节点的数量。
改进思路：
关键在于利用二叉搜索树的特性，通过中序遍历来实现高效的求解。中序遍历会按照从小到大的顺序遍历树的节点，因此我们可以利用这个特性直接找到第k小的元素，而无需先将所有元素存储到列表中再进行排序。
改进的思路：
- 中序遍历：通过递归的方式遍历二叉树的左子树、当前节点、右子树，能在遍历的过程中按顺序访问到每个节点。
- 利用计数：在中序遍历过程中，记录当前已经访问到的节点数量。当访问到第
k个节点时，直接返回该节点的值。
这样可以避免不必要的排序操作，将时间复杂度降低到O(n)，其中n是树中节点的数量。
/*** Definition for a binary tree node.* public class TreeNode {* int val;* TreeNode left;* TreeNode right;* TreeNode() {}* TreeNode(int val) { this.val = val; }* TreeNode(int val, TreeNode left, TreeNode right) {* this.val = val;* this.left = left;* this.right = right;* }* }*/
class Solution {private int count = 0; // 用来记录访问的节点数private int result = 0; // 存储第k小的值/*** 通过中序遍历找到二叉搜索树中的第k小的元素* * @param root 二叉搜索树的根节点* @param k 第k小的元素* @return 第k小的元素*/public int kthSmallest(TreeNode root, int k) {// 调用中序遍历inorder(root, k);return result;}/*** 中序遍历，递归访问节点，直到找到第k小的节点。* * @param root 当前节点* @param k 第k小的元素*/private void inorder(TreeNode root, int k) {// 如果当前节点为空，直接返回if (root == null) {return;}// 先遍历左子树inorder(root.left, k); // 访问当前节点count++; // 访问节点计数if (count == k) {result = root.val; // 找到第k小的节点，记录其值return; // 找到后立即返回，结束递归} // 如果还没有找到，继续遍历右子树inorder(root.right, k);}
}
- 时间复杂度：O(n)，其中
n是二叉树中的节点数量。我们只需要遍历树的节点，直到找到第k小的元素为止，最坏情况下会遍历整个树。 - 空间复杂度：O(h)，其中
h是树的高度。递归调用栈的深度最大为树的高度，对于平衡二叉树，h大约为log n，对于不平衡的树，h最大为n。 
