230. Kth Smallest Element in a BST
Medium
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
.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | /** * 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: int kthSmallest(TreeNode* root, int k) { int nLeft = countN(root->left); if(k==nLeft+1) return root->val; else if(k<=nLeft) return kthSmallest(root->left, k); else return kthSmallest(root->right, k-nLeft-1); } int countN(TreeNode* root){ if(!root) return 0; return 1+countN(root->left)+countN(root->right); } }; |
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: int kthSmallest(TreeNode* root, int k) { int ret, cur = k; dfs(root, cur, ret); return ret; } void dfs(TreeNode* root, int &cur, int &ret){ if(!root) return; dfs(root->left, cur, ret); cur--; if(cur==0) ret = root->val; dfs(root->right, cur, ret); } }; |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { int left, ret; public int kthSmallest(TreeNode root, int k) { left = k; dfs(root); return ret; } void dfs(TreeNode node){ if(node==null) return; dfs(node.left); left--; if(left==0) ret = node.val; dfs(node.right); } } |
No comments:
Post a Comment