如何分析网站功能,h5 和手机网站,wordpress qq微信,网站建设公司推荐互赢网络给定一个二叉搜索树#xff0c;编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。 说明#xff1a; 你可以假设 k 总是有效的#xff0c;1 ≤ k ≤ 二叉搜索树元素个数。 示例 1: 输入: root [3,1,4,null,2], k 1 3 / \ 1 4 \ 2 输出: 1 示例 2: 输入… 给定一个二叉搜索树编写一个函数 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 函数 解法一
class Solution
{
public:int kthSmallest(TreeNode* root, int k) {vectorint num;help(root, num); return num[k-1];}void help(TreeNode *root, vectorint num){if(!root) return;help(root-left, num);num.push_back(root-val);help(root-right, num);}
};
解法二:
class Solution
{
public:int kthSmallest(TreeNode* root, int k) {int num -1;help(root, k); }void help(TreeNode *root, int k, int num){if(!root) return;help(root-left, k, num);if(0 --k){num root-val;return;}help(root-right, k, num);}
};
