题目：
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?
思路：
就是inorder traverse
1 public int kthSmallest(TreeNode root, int k) 2 { 3 4 ArrayList<Integer> re = new ArrayList<Integer>(); 5 // if(root==null) 6 // return re; 7 helper(root,re); 8 return re.get(k-1); 9 10 } 11 12 public void helper(TreeNode root, ArrayList<Integer> re) 13 { 14 if(root==null) 15 return; 16 helper(root.left,re); 17 re.add(root.val); 18 helper(root.right,re); 19 }
reference：http://www.programcreek.com/2014/07/leetcode-kth-smallest-element-in-a-bst-java/
*Kth Smallest Element in a BST
原文：http://www.cnblogs.com/hygeia/p/4772083.html