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?

Hint:

1. Try to utilize the property of a BST.
2. What if you could modify the BST node's structure?

中序遍历，Morris，线索二叉树……。

1 /** 2  * Definition for a binary tree node. 3  * struct TreeNode { 4  *     int val; 5  *     TreeNode *left; 6  *     TreeNode *right; 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {} 8  * }; 9  */10 class Solution {11 public:12     int kthSmallest(TreeNode* root, int k) {13         int cnt = 0;14         TreeNode *p = root;15         stack
     
       st;16         while (p != NULL || !st.empty()) {17             if (p != NULL) {18                 st.push(p);19                 p = p->left;20             } else {21                 p = st.top();22                 st.pop();23                 if (++cnt == k) return p->val;24                 p = p->right;25             }26         }27     }28 };