Given a binary search tree, write a functionkthSmallestto find thekth 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:Try to utilize the PRoperty of a BST.

這道題和之前那個next() method的差不多，不過多了一個k值在這里。

題目以及提示了我們要借助BTS的definition來做，遵循這樣的順序：左<根<右

因此在最開始我們先add了所有最右邊的treenode后，并不是就萬事大吉了，結點之間的右邊的Node們同樣重要。

舉例：stack.pop()出目前的最小值后（只store了左邊的treenode的情況下），再pop（）一次就一定是第二小的嗎？肯定不是的，如果這個最小值的node的node.right!=null的話，很明顯node.right的值會小于倒數第二個結點。(說的有點混亂，可畫圖理解=。=）

因此我們再pop()出目前最小值后，再第二次pop()之前應該馬上檢測其Node.right并把這些值都按順序store進stack，然后再借助if statement第二次運行。

代碼如下。~

public class Solution {    public int kthSmallest(TreeNode root, int k) {    Stack<TreeNode> stack = new Stack<TreeNode>();    TreeNode p = root;    int result = 0;     while(!stack.isEmpty() || p!=null){        if(p!=null){            stack.push(p);            p = p.left;        }else{            TreeNode temp = stack.pop();            k--;            if(k==0){                result = temp.val;            }            p = temp.right;        }    }     return result;}}