|
马上注册,结交更多好友,享用更多功能^_^
您需要 登录 才可以下载或查看,没有账号?立即注册
x
- 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.
- 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?
复制代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public int kthSmallest(TreeNode root, int k) {
- List<Integer> list = new ArrayList<>();
- if(root == null) return 0;
- help(root,list);
- Integer[] re = new Integer[list.size()];
- list.toArray(re);
- Arrays.sort(re);
-
- return re[k-1];
- }
- public void help(TreeNode root, List<Integer> list){
- if(root == null) return;
- if(root != null){
- help(root.left,list);
- list.add(root.val);
- help(root.right,list);
- }
- }
- }
复制代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public int kthSmallest(TreeNode root, int k) {
- List<Integer> list = new ArrayList<>();
- if(root == null) return 0;
- help(root,list);
- Integer[] re = new Integer[list.size()+1];
-
- for(int i = 0; i < list.size(); i++){
- re[list.get(i)] = 0;
- re[list.get(i)]++;
- }
- for(int i = 0; i< re.length; i++){
- if(re[i] == null) continue;
- if(re[i] == 1) k--;
- if(k == 0) return i;
- }
- return 0;
- }
- public void help(TreeNode root, List<Integer> list){
- if(root == null) return;
- if(root != null){
- help(root.left,list);
- list.add(root.val);
- help(root.right,list);
- }
- }
- }
复制代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- public int kthSmallest(TreeNode root, int k) {
- List<Integer> list = new ArrayList<>();
- if(root == null) return 0;
- help(root,list);
-
- return list.get(k-1);
- }
- public void help(TreeNode root, List<Integer> list){
- if(root == null) return;
- if(root != null){
- help(root.left,list);
- list.add(root.val);
- help(root.right,list);
- }
- }
- }
复制代码
- /**
- * Definition for a binary tree node.
- * public class TreeNode {
- * int val;
- * TreeNode left;
- * TreeNode right;
- * TreeNode(int x) { val = x; }
- * }
- */
- class Solution {
- int kth = 0;
- int result = 0;
- public int kthSmallest(TreeNode root, int k) {
- kth = k;
- help(root);
- return result;
-
- }
- private void help(TreeNode root){
- if(root == null || kth == 0) return;
-
- help(root.left);
- kth--;
- if(kth == 0) result = root.val;
- help(root.right);
- }
- }
复制代码 |
|