当前位置：首页 > backend >正文

leetcode0230. 二叉搜索树中第 K 小的元素-medium

backend 2025/5/6 19:19:40

1 题目：二叉搜索树中第 K 小的元素

官方标定难度：中

给定一个二叉搜索树的根节点 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 小的值，你将如何优化算法？

2 solution

中序遍历二叉树，找到其中第 k 个遍历的数。

代码

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {/** 中序遍历第 k 个** 进阶：如果频繁被修改，应该考虑将每个子树的数量存储下来，结合修改操作进行加减*/int u = -1;int t;void dfs(TreeNode *root) {if (!root) return;dfs(root->left);t--;if (!t) {u = root->val;return;}dfs(root->right);}public:int kthSmallest(TreeNode *root, int k) {t = k;dfs(root);return u;}
};