230. Kth Smallest Element in a BST

#### QUESTION:

Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.

Note: You may assume k is always valid, 1 ≤ k ≤ BST’s total elements.

Example 1:

``````Input: root = [3,1,4,null,2], k = 1
3
/ \
1   4
\
2
Output: 1
``````

Example 2:

``````Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3   6
/ \
2   4
/
1
Output: 3
``````

Follow up: 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?

#### EXPLANATION:

1. 定义两个值，一个用来表示摊平到第几个数，一个用来表示最后的结果
2. 采用先序遍历的方式，遍历树
3. 每次遍历到root时，就将索引进行+1
4. 当索引为k的时候，表示已经遍历到了第k个小的值
5. 当索引比k大时，则可以直接返回

#### SOLUTION:

``````class Solution {
public  int kthSmallestResult = 0;
public  int kthSmallestIndex = 0;
public  int kthSmallest(TreeNode root, int k) {
if(root==null) return 0;
kthSmallest(root.left,k);
kthSmallestIndex++;
if(kthSmallestIndex == k)
kthSmallestResult = root.val;
if(kthSmallestIndex < k)
kthSmallest(root.right,k);
return kthSmallestResult;
}
}
``````