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)