Description
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example
Example 1:
Input：{1,#,2},2
Output：2
Explanation：
1
\
2
The second smallest element is 2.
Example 2:
Input：{2,1,3},1
Output：1
Explanation：
2
/ \
1 3
The first smallest element is 1.
Challenge
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
思路：
总体就是中序遍历的第K个点即为答案， 有递归和非递归两种实现方法，递归又有用全局变量或者传参数两种方法。非递归的中序遍历要用到栈的概念，答案还用了个dummy node节省了对于根节点非空的判断。
代码：
递归的使用传参数的方法：
非递归的方法：
网友评论