本文共 1222 字,大约阅读时间需要 4 分钟。
给定一个二叉搜索树,编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明:
你可以假设 k 总是有效的,1 ≤ k ≤ 二叉搜索树元素个数。示例 1:
输入: root = [3,1,4,null,2], k = 1
3 / \ 1 4 \ 2
输出: 1
示例 2:输入: root = [5,3,6,2,4,null,null,1], k = 3
5 / \ 3 6 / \ 2 4 / 1
输出: 3
进阶: 如果二叉搜索树经常被修改(插入/删除操作)并且你需要频繁地查找第 k 小的值,你将如何优化 kthSmallest 函数?来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/kth-smallest-element-in-a-bst 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
/** * 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 seq; int ans;public: int kthSmallest(TreeNode* root, int k) { seq = 0; dfs(root, k); return ans; } void dfs(TreeNode* root, int k) { if (!root) { return; } dfs(root->left, k); //中序遍历 seq++; if (seq == k) { ans = root->val; return; } dfs(root->right, k); }};