Kth smallest Element in a BST
题目描述
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?
解题方法
in-order traversal
用stack，当达到第k个的时候，就是第k个
follow-up
如果可以更改原来的bst,在node中新增一个variable, left_count，记录左子树中的 node的数量