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?

Credits:

Special thanks to @ts for adding this problem and creating all test cases.

Solution:

这道题就是典型的中序遍历的题目，一定要记住用循环加堆栈实现的方式。如果要是求第K个大的呢，这个时候就需要灵活的考虑，就变成了右根左的，中序遍历了，道理是一样的，树所有的问题都是可以这样展开分析的。

class Solution(object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        stack = []
        curr = root

        while stack or curr:
            while curr:
                stack.append(curr)
                curr = curr.left
            curr = stack.pop()
            k -= 1
            if k == 0:
                return curr.val
            curr = curr.right
        return 0