我是靠谱客的博主 拼搏店员,这篇文章主要介绍Leetcode 230. 二叉搜索树中第K小的元素,现在分享给大家,希望可以做个参考。

记录每个节点为跟的树的节点个数,然后进行查找,若删除,添加只需要Oh的复杂度来更改节点个数

复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: map<TreeNode*,int> cnt; int init(TreeNode* root){ if(!root) return 0; return (cnt[root]=1+init(root->left)+init(root->right)); } int kthSmallest(TreeNode* root, int k) { cnt[NULL]=0; init(root); if(k==cnt[root->left]+1) return root->val; else if(k>cnt[root->left]+1) return kthSmallest(root->right,k-cnt[root->left]-1); else return kthSmallest(root->left,k); } };

最后

以上就是拼搏店员最近收集整理的关于Leetcode 230. 二叉搜索树中第K小的元素的全部内容,更多相关Leetcode内容请搜索靠谱客的其他文章。

本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
点赞(106)

评论列表共有 0 条评论

立即
投稿
返回
顶部