Leetcode 230.二叉搜索树中第k小的元素

Posted on |

230.二叉搜索树中第k小的元素

题目

给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。

说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
示例 1:

输入: root = [3,1,4,null,2], k = 1
   3
  / \
 1   4
  \
   2
输出: 1
示例 2:

输入: root = [5,3,6,2,4,null,null,1], k = 3
       5
      / \
     3   6
    / \
   2   4
  /
 1
输出: 3

进阶：
如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 k 小的值，你将如何优化 kthSmallest 函数？

方法

方法1：递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 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
        """
        res = []
        self.search(res,root)
        return res[k-1]
    def search(self,res,root):
        if not root:
            return
        self.search(res,root.left)
        res.append(root.val)
        self.search(res,root.right)
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
# 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
        """
        Order = self.getOrder(root)
        return Order[k-1]

    def getOrder(self,root):
        result = []
        if root.left:
            result += self.getOrder(root.left)
        result.append(root.val)
        if root.right:
            result += self.getOrder(root.right)
        return result
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
# 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 countNodes(self, root): # 计算子树的节点数
        if root == None:
            return 0            # 此处不是None，是0
        else:
            return 1 + self.countNodes(root.left) + self.countNodes(root.right)

    def kthSmallest(self, root, k):
        """
        :type root: TreeNode
        :type k: int
        :rtype: int
        """
        # 先遍历所有的值，然后找到第k小的数字，最后利用二分搜索进行处理
        if root == None:
            return None
        leftCount = self.countNodes(root.left)
        if k <= leftCount:
            return self.kthSmallest(root.left, k)
        elif k == leftCount + 1:
            return root.val
        else:
            return self.kthSmallest(root.right, k - 1 - leftCount)