你的位置:首页 > Java教程

[Java教程][LeetCode] 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?

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