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.

Example 1:

Input: root = [3,1,4,null,2], k = 1
 Output: 1
 Example 2:

Input: root = [5,3,6,2,4,null,null,1], k = 3
 Output: 3
 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? 

 
int kthSmallest(struct TreeNode* root, int k) 
{
    struct TreeNode **stack = NULL;   
    int cur = 0;
    struct TreeNode * p = root;
    struct TreeNode * res = NULL;
    
    while(p || cur>0)
    {
        while(p)
        {
            /*入栈*/
            stack = (struct TreeNode **)realloc(stack,sizeof(struct TreeNode *) * (cur + 1));
            stack[cur++] = p;
            p = p->left;
        }
        
        res = stack[--cur];
        
        if(0 == --k)
            return res->val;
        
        p = res->right;
        
    }
    
    return 0;
}