本文主要是介绍每日OJ题_二叉树dfs⑤_力扣230. 二叉搜索树中第K小的元素，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
目录
力扣230. 二叉搜索树中第K小的元素
解析代码
力扣230. 二叉搜索树中第K小的元素
230. 二叉搜索树中第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^40 <= Node.val <= 10^4
进阶：如果二叉搜索树经常被修改（插入/删除操作）并且你需要频繁地查找第 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 {
public:int kthSmallest(TreeNode* root, int k) {};解析代码
思路就是中序遍历到第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 {int cnt = 0, ret = 0;
public:int kthSmallest(TreeNode* root, int k) {cnt = k;dfs(root);return ret;}void dfs(TreeNode* root){if(root == nullptr || cnt == 0)return;dfs(root->left); // 遍历左子树if(--cnt == 0) // 判断ret = root->val;dfs(root->right); // 遍历右子树}
};这篇关于每日OJ题_二叉树dfs⑤_力扣230. 二叉搜索树中第K小的元素的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
