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?
Credits:
Special thanks to @ts for adding this problem and creating all test cases.
利用中序遍历， 与前面2个题思路一样。
1 class Solution { 2 public int kthSmallest(TreeNode root, int k) { 3 if(root==null) return 0; 4 TreeNode cur = root; 5 Stack<TreeNode> stack = new Stack<TreeNode>(); 6 while(cur!=null ||!stack.isEmpty()){ 7 while(cur!= null){ 8 stack.push(cur); 9 cur = cur.left; 10 } 11 cur = stack.pop(); 12 k--; 13 if(k==0) return cur.val; 14 cur = cur.right; 15 } 16 return 0; 17 } 18 }