[LeetCode] Kth Smallest Element in a BST

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;}}