首页leetcode 230

leetcode 230

时间: 2023-08-27 19:06:55 浏览: 174

题目描述：给定一个二叉搜索树的根节点 root 和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。示例 1： ``` 输入：root = [3,1,4,null,2], k = 1 输出：1 ``` 示例 2： ``` 输入：root = [5,3,6,2,4,null,null,1], k = 3 输出：3 ``` 提示： * 树中的节点数为 n 。 * 1 <= k <= n <= 10^4 * 0 <= Node.val <= 10^4 解题思路：二叉搜索树的中序遍历是递增的，所以我们可以通过中序遍历来得到第 k 个最小的元素。具体地，我们可以通过迭代的方式得到中序遍历的第 k 个节点，中序遍历的迭代实现方法需要借助栈来实现。每次迭代的时候，我们先将当前节点的所有左子节点放入栈中，然后弹出栈顶的节点，如果弹出的是第 k 个节点，那么我们就返回这个节点的值，否则我们就继续遍历右子节点。时间复杂度：O(H+k)，其中 H 是树的高度，由于我们开始遍历之前，要先向下达到叶，当树是一个平衡树时：复杂度为 O(logN+k)；当树是一个不平衡树时：复杂度为 O(N+k)。空间复杂度：O(H)，其中 H 是树的高度，最坏的情况下需要空间 O(N)，当树退化为链表时。参考代码： ```python class Solution: def kthSmallest(self, root: TreeNode, k: int) -> int: stack = [] while True: while root: stack.append(root) root = root.left root = stack.pop() k -= 1 if not k: return root.val root = root.right ```

阅读全文