Given a binary search tree, write a function kthSmallest
to find the kth smallest element in it.
Example 1:
Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3 5 / \ 3 6 / \ 2 4 / 1 Output: 3
Follow up:
What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
Constraints:
- The number of elements of the BST is between
1
to10^4
. - You may assume
k
is always valid,1 ≤ k ≤ BST's total elements
.
就是每次计算左子树的大小---------------会有重复计算的问题--------------
/** * 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 { private: int getCount(TreeNode* root){ if(! root){ return 0; } return 1 + getCount(root->left) + getCount(root->right); } public: int kthSmallest(TreeNode* root, int k) { // we can assume root is not NULL int lCount = getCount(root->left); if(k <= lCount){ return kthSmallest(root->left, k); }else if(k == lCount +1 ){ return root->val; }else{ return kthSmallest(root->right, k-lCount-1); } } };
----------------------------------最多走一遍---------利用了 C++ 的参数 引用------------------
/** * 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 { private: int helper(TreeNode* root, int& k){ if(not root){ return INT_MIN; } int l = helper(root->left, k); if(l != INT_MIN){ // left found nothing return l; } if(k==1){ return root->val; } --k; return helper(root->right, k); } public: int kthSmallest(TreeNode* root, int k) { return helper(root, k); } };
Mistakes:
1: 如果想通过监控res 是否是nullptr, 那么需要 double Pointer
No comments:
Post a Comment