[Leetcode] Kth Smallest Element in a BST 二叉搜索树第k小节

Dean 发布于2019-08-14 12:26 / 2902人阅读

摘要：中序遍历复杂度时间空间思路因为左节点小于根节点小于右节点，二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式，我们就可以在找到第小节点时马上退出。这样我们就可以用二叉树搜索的方法来解决这个问题了。

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).

中序遍历 复杂度

时间 O(N) 空间 O(N)

思路

因为左节点小于根节点小于右节点，二叉搜索树的一个特性就是中序遍历的结果就是树内节点从小到大顺序输出的结果。这里采用迭代形式，我们就可以在找到第k小节点时马上退出。中序遍历详见Binary Tree Traversal。

代码

public class Solution {
    public int kthSmallest(TreeNode root, int k) {
        Stack s = new Stack();
        while(root!=null){
            s.push(root);
            root = root.left;
        }
        while(!s.isEmpty()){
            TreeNode curr = s.pop();
            k--;
            if(k == 0) return curr.val;
            if(curr.right != null){
                curr = curr.right;
                while(curr!=null){
                    s.push(curr);
                    curr = curr.left;
                }
            }
        }
        return 0;
    }
}

后续 Follow Up

这题的难点其实在于Follow Up：如果我们频繁的操作该树，并且频繁的调用kth函数，有什么优化方法使时间复杂度降低至O(h)？h是树的高度。根据提示，我们可以在TreeNode中加入一个rank成员，这个变量记录的是该节点的左子树中节点的个数，其实就是有多少个节点比该节点小。这样我们就可以用二叉树搜索的方法来解决这个问题了。这个添加rank的操作可以在建树的时候一起完成。

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/64482.html

[Leetcode-Tree] Kth Smallest Element in a BST

摘要：解题思路本题需要找的是第小的节点值，而二叉搜索树的中序遍历正好是数值从小到大排序的，那么这题就和中序遍历一个情况。 Kth Smallest Element in a BSTGiven a binary search tree, write a function kthSmallest to find the kth smallest element in it. Note: You ...

Carl 2019-08-16 10:26 评论0 收藏0
Kth Smallest Element in a BST

摘要：题目链接二分找结果，按左边数来分如果改下，加入的，那就可以在时间内找到结果了 Kth Smallest Element in a BST 题目链接：https://leetcode.com/problems... inorder traverse： public class Solution { public int kthSmallest(TreeNode root, int...

Barry_Ng 2019-08-14 17:26 评论0 收藏0
leetcode 315 Count of Smaller Numbers After Self 以

摘要：题目意思就是要一个个的返回当前的最小值。所以解法自然就是。我们需要找出被打乱的点并返回正确结果。然后将两个不正确的点记录下来，最后回原来正确的值。如果是叶子节点，或者只有一个子树。思想来自于的代码实现。跳过总结请点这里：https://segmentfault.com/a/11... BST最明显的特点就是root.left.val < root.val < root.right.v...

inapt 2019-08-14 17:20 评论0 收藏0
[LeetCode] 378. Kth Smallest Element in a Sorted M

摘要：先放一行，或一列把堆顶的最小元素取出来，取次，如果该有下一行下一列的，放入堆中最小的个元素已经在上面的循环被完了，下一个堆顶元素就是 Problem Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in...

Shihira 2019-08-16 13:43 评论0 收藏0
leetcode378. Kth Smallest Element in a Sorted Matr

摘要：因此我们可以采用部分元素堆排序即可。即我们每次只需要可能构成第个元素的值进行堆排序就可以了。题目要求 Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix. Note that...

dailybird 2019-08-16 15:05 评论0 收藏0