脚本宝典收集整理的这篇文章主要介绍了[Leetcode-Tree] Kth Smallest Element in a BST,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
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.
What if you could modify the BST node's structure?
The optimal runtime complexity is O(height of BST).
1.解题思路
本题需要找的是第k小的节点值,而二叉搜索树的中序遍历正好是数值从小到大排序的,那么这题就和中序遍历一个情况。
public class Solution {
Stack<TreeNode> s=new Stack<TreeNode>();
public int kthSmallest(TreeNode root, int k) {
if(root==null) return 0;
pushLeft(root);
while(!s.empty()){
TreeNode node=s.pop();
if(--k==0) return node.val;
if(node.right!=null)
pushLeft(node.right);
}
return 0;
}
private void pushLeft(TreeNode root){
TreeNode node=root;
while(node!=null){
s.push(node);
node=node.left;
}
}
}
3.Follow up
如果树会经常被更改,为了效率,我们可以对树的构造稍作变更,添加一个属性,来标明该节点拥有的左子树的节点数,而这个Number就是比当前值小的节点个数,这样我们结合二分法,就很容易找到第k个小的节点值。
以上是脚本宝典为你收集整理的[Leetcode-Tree] Kth Smallest Element in a BST全部内容,希望文章能够帮你解决[Leetcode-Tree] Kth Smallest Element in a BST所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。