文章目录
1. 题目
给定一个二叉搜索树的根节点 root
,和一个整数 k
,请你设计一个算法查找其中第 k
个最小元素(从
1
1
1 开始计数)。
1.1 示例
-
示例 1 1 1 :
-
输入:
root = [3, 1, 4, null, 2]
,k = 1
- 输出: 1 1 1
-
输入:
-
示例 2 2 2 :
-
输入:
root = [5, 3, 6, 2, 4, null, null, 1]
,k = 3
- 输出: 3 3 3
-
输入:
1.2 说明
- 来源: 力扣(LeetCode)
- 链接: https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst
1.3 限制
- 树中的节点数为 n n n ;
- 1 ≤ k ≤ n ≤ 1 0 4 1 \le k \le n \le 10^4 1≤k≤n≤104 ;
- 0 ≤ N o d e . v a l ≤ 1 0 4 0 \le Node.val \le 10^4 0≤Node.val≤104 。
1.4 进阶
如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k
小的值,你将如何优化算法?
2. 解法一(递归中序遍历)
2.1 分析
实际上,由于题目指出这里给定的是一棵二叉搜索树,而由【数据结构Python描述】二叉搜索树简介与使用二叉搜索树实现有序映射可知,二叉搜索树有一个特殊的性质,即其中序遍历的结果是一个有序的递增序列,利用此性质可以方便地给出如下递归解法:
2.2 实现
from typing import Optional, List
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def _kth_smallest(self, root: Optional[TreeNode], tree: List[int]):
if not root:
return
self._kth_smallest(root.left, tree)
tree.append(root.val)
self._kth_smallest(root.right, tree)
def kth_smallest(self, root: Optional[TreeNode], k: int) -> Optional[int]:
tree = []
self._kth_smallest(root, tree)
print(tree)
return tree[k - 1]
def main():
node6 = TreeNode(1)
node5 = TreeNode(4)
node4 = TreeNode(2, left=node6)
node3 = TreeNode(6)
node2 = TreeNode(3, left=node4, right=node5)
node1 = TreeNode(5, left=node2, right=node3)
root = node1
sln = Solution()
print(sln.kth_smallest(root, 3)) # 3
if __name__ == '__main__':
main()
2.3 复杂度
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)