【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)
2021/11/14 23:41:23
本文主要是介绍【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
文章目录
- 1. 题目
- 1.1 示例
- 1.2 说明
- 1.3 限制
- 1.4 进阶
- 2. 解法一(递归中序遍历)
- 2.1 分析
- 2.2 实现
- 2.3 复杂度
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)
这篇关于【LeetCode 二叉树专项】二叉搜索树中第 K 小的元素(230)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01UniApp 中组件的生命周期是多少-icode9专业技术文章分享
- 2024-11-01如何使用Svg Sprite Icon简化网页图标管理
- 2024-10-31Excel数据导出课程:新手从入门到精通的实用教程
- 2024-10-31Excel数据导入课程:新手入门指南
- 2024-10-31RBAC的权限课程:新手入门教程
- 2024-10-31Svg Sprite Icon课程:新手入门必备指南
- 2024-10-31怎么配置 L2TP 允许多用户连接-icode9专业技术文章分享
- 2024-10-31怎么在FreeBSD上 安装 OpenResty-icode9专业技术文章分享
- 2024-10-31运行 modprobe l2tp_ppp 时收到“module not found”消息提醒是什么-icode9专业技术文章分享
- 2024-10-31FreeBSD的下载命令有哪些-icode9专业技术文章分享