问题：

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.

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?

解决：

① 借助中序遍历。

class Solution {//3ms

    public int kthSmallest(TreeNode root, int k) {         List<Integer> list = new ArrayList<>();         inorder(root,list);         int res = list.get(k - 1);         return res;     }     public void inorder(TreeNode root,List<Integer> list){         if (root == null) return;         inorder(root.left,list);         list.add(root.val);         inorder(root.right,list);     } }

② 借助栈实现中序遍历。

class Solution {//2ms

    public int kthSmallest(TreeNode root, int k) {         Stack<TreeNode> stack = new Stack<>();         TreeNode cur = root;         while (cur != null){             stack.push(cur);             cur = cur.left;         }         int count = 0;         while (! stack.isEmpty()){             cur = stack.pop();             count ++;             if (count == k){                 return cur.val;             }             TreeNode tmp = cur.right;             while (tmp != null){                 stack.push(tmp);                 tmp = tmp.left;             }         }         return -1;     } }

③ 在中序遍历过程中查找第k小的值。

class Solution { //0ms

    int count = 0;     int res = 0;     public int kthSmallest(TreeNode root, int k) {         count = k - 1;         inorder(root);         return res;     }     public void inorder(TreeNode root){         if (root == null || count < 0){             return;         }         inorder(root.left);         if (count == 0){             res = root.val;             count --;         }         count --;         inorder(root.right);              } }