Given a binary search tree, write a function
kthSmallest
to find the kth smallest element in it.
Note:
You may assume k is always valid, 1 ? k ? BST's total elements.
You may assume k is always valid, 1 ? k ? BST's total elements.
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?
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?
[Thoughts]
递归遍历二叉树,在遍历过程中算kth。
[Code]
1: int kthSmallest(TreeNode* root, int k) {
2: int count = 0;
3:
4: return kthSmallestImpl(root, count, k);
5:
6: }
7:
8: int kthSmallestImpl(TreeNode* root, int& count, int k) {
9: if(root == NULL) return -1;
10:
11: int lr = kthSmallestImpl(root->left, count, k);
12: count++;
13: if(count == k) {
14: return root->val;
15: }
16:
17: int rr = kthSmallestImpl(root->right, count, k);
18: return lr != -1 ? lr : rr;
19: }
3 comments:
Very Nice Post, I learned a lot through it. Thanks for posting.
digitizing for embroidery
Nice post I have learned a lot throughout this blog thanks for sharing keep it up. by cheap digitizing embroidery
Elevate your daily routine with Apna Showroom’s divine grooming set. This bundle includes Gangajal Kalash Lota from Har Ki Pauri, a powerful Shaligram Shivling, a pretty rose brooch, a lice comb, and a hair comb made for women and girls.Apna Showroom Women's net Fishnet Lingerie Stockings - Fishnet Stockings for women - (Black Free Size) Pack of 2
Apna Showroom Baby Boy's and Girl's Night Suit for 0-6 Months Combo Set Pair of 2 (4 Pieces) Newborn Baby Night Suits cotton with desent Look
Apna Showroom Women's Nylon Underskirt Pantyhose Stockings for women - (Black Free Size) Pack of 1
Novasox Ankle High Fishnet Mesh Women Socks, Women Fishnet Mesh Ankle Socks
Apna Showroom Men's and Women's Metal Hair Bands (Black) Combo set of 5
The hair comb is designed for effortless styling and comfort. Perfect for temple use, as festival prasad, or thoughtful gifting, this combo merges sacred energy with self-care—encouraging balance, cleanliness, and devotion in every home.
Post a Comment