首页 > itarticle > 230 kth smallest element in a bst

230 kth smallest element in a bst

admin 1月 11, 2021 0

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:

  1. Try to utilize the property of a BST.
  2. What if you could modify the BST node’s structure?
  3. The optimal runtime complexity is O(height of BST).

思路

根据平衡二叉树的性质，对平衡二叉树中序遍历，生成的数组是升序的。

所以利用深度优先遍历，将中序遍历的第k个结果输出即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
 
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
class (object):
    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        self.res = []
        if (root):
            self.search(root, k)
        
        return self.res[-1]
        
    def search(self, cur, k):
        if(cur.left):
            self.search(cur.left, k)
        
        if (len(self.res) == k):
            return
        else:
            self.res.append(cur.val)
            
        if(cur.right):
            self.search(cur.right, k)
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能