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
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(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)