二叉搜索树中第K小的元素的思路探讨与源码
????二叉搜索树中第K小的元素的题目如下图，该题属于搜索类和树类型的题目，主要考察对于搜索方法的使用和树结构的理解。本文的题目作者想到2种方法，分别是中序遍历方法和优先队列方法，其中优先队列方法使用Java进行编写，而中序遍历方法使用Python进行编写，当然这可能不是最优的解法，还希望各位大佬给出更快的算法。
????本人认为该题目可以使用优先队列方法的思路进行解决，首先初始化一个存放数字的优先队列，初始化一个存放树节点的队列，并将树节点放入队列里面。开始遍历队列，只要队列不是空，就进入到循环内部，将队列的头部元素拿出，然后判断优先队列的大小是否比指定数字k要小，如果是就把当前树节点的值加入到优先队列里面去；如果优先队列的第一个元素比树节点的当前值要大，那么就把队列头部元素移除，并在尾部加入当前树节点的值。继续进行判断，如果当前节点的左子节点不是空，就把左子节点加入到双端队列的尾部；如果当前节点的右子节点不是空，就把右子节点加入到双端队列的尾部。最终返回循环遍历结束后优先队列的头部元素值的结果即可。那么按照这个思路我们的Java代码如下：
#喷火龙与水箭龟
class Solution {
public int kthSmallest(TreeNode root, int k) {
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>((m,n)->n-m);
Deque<TreeNode> deque = new ArrayDeque<>();
deque.addLast(root);
while (!deque.isEmpty()) {
TreeNode vex = deque.pollFirst();
if (priorityQueue.size() < k) {
priorityQueue.add(vex.val);
}
else if (priorityQueue.peek() > vex.val) {
priorityQueue.poll();
priorityQueue.add(vex.val);
}
if(vex.left != null){
deque.addLast(vex.left);
}
if(vex.right != null){
deque.addLast(vex.right);
}
}
return priorityQueue.peek();
}
}
????显然，我们看到优先队列的方法效果比较一般，同时还可以使用中序遍历方法解决。首先初始化一个列表，然后开始遍历树，将树的当前元素加入到列表里面，并继续访问左子节点，只要左子节点不是空，就继续将节点元素加入到列表里面。进行完上述操作以后，将列表尾部的元素拿出，并把指定的K值减去1，判断K值是否为0，如果是就可以直接返回当前元素值，如果不是就把当前元素的右子节点赋值给当前元素并继续访问，直到最终找到第K小的元素。所以按照这个思路就可以解决，下面是Python代码：
#喷火龙与水箭龟
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
midList = []
while root or midList:
while root:
midList.append(root)
root = root.left
root = midList.pop()
k = k - 1
if(k == 0):
return root.val
root = root.right
????从结果来说Java版本的优先队列方法的效率比较差，而Python版本的中序遍历方法的速度还可以，但应该是有更多的方法可以进一步提速的，希望朋友们能够多多指教，非常感谢。