leetcode 230. Kth Smallest Element in a BST
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 = , k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:
Input: root = , 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.toArray(re);
Arrays.sort(re);
return re;
}
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;
for(int i = 0; i < list.size(); i++){
re = 0;
re++;
}
for(int i = 0; i< re.length; i++){
if(re == null) continue;
if(re == 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);
}
}
页:
[1]