leetcode 230. Kth Smallest Element in a BST

Seawolf

1. Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
   
2. 
   
3. Note:
   
4. You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
   
5. 
   
6. Example 1:
   
7. 
   
8. Input: root = [3,1,4,null,2], k = 1
   
9.    3
   
10.   / \
    
11. 1   4
    
12.   \
    
13.    2
    
14. Output: 1
    
15. Example 2:
    
16. 
    
17. Input: root = [5,3,6,2,4,null,null,1], k = 3
    
18.        5
    
19.       / \
    
20.      3   6
    
21.     / \
    
22.    2   4
    
23.   /
    
24. 1
    
25. Output: 3
    
26. Follow up:
    
27. 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?

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public int kthSmallest(TreeNode root, int k) {
    
12.         List<Integer> list = new ArrayList<>();
    
13.         if(root == null) return 0;
    
14.         help(root,list);
    
15.         Integer[] re = new Integer[list.size()];
    
16.         list.toArray(re);
    
17.         Arrays.sort(re);
    
18.         
    
19.         return re[k-1];
    
20.     }
    
21.     public void help(TreeNode root, List<Integer> list){
    
22.         if(root == null) return;
    
23.         if(root != null){
    
24.             help(root.left,list);
    
25.             list.add(root.val);
    
26.             help(root.right,list);
    
27.         }
    
28.     }
    
29. }

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public int kthSmallest(TreeNode root, int k) {
    
12.         List<Integer> list = new ArrayList<>();
    
13.         if(root == null) return 0;
    
14.         help(root,list);
    
15.         Integer[] re = new Integer[list.size()+1];
    
16.         
    
17.         for(int i = 0; i < list.size(); i++){
    
18.             re[list.get(i)] = 0;
    
19.             re[list.get(i)]++;
    
20.         }
    
21.         for(int i = 0; i< re.length; i++){
    
22.             if(re[i] == null) continue;
    
23.             if(re[i] == 1) k--;
    
24.             if(k == 0) return i;
    
25.         }
    
26.         return 0;
    
27.     }
    
28.     public void help(TreeNode root, List<Integer> list){
    
29.         if(root == null) return;
    
30.         if(root != null){
    
31.             help(root.left,list);
    
32.             list.add(root.val);
    
33.             help(root.right,list);
    
34.         }
    
35.     }
    
36. }

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     public int kthSmallest(TreeNode root, int k) {
    
12.         List<Integer> list = new ArrayList<>();
    
13.         if(root == null) return 0;
    
14.         help(root,list);
    
15.         
    
16.         return list.get(k-1);
    
17.     }
    
18.     public void help(TreeNode root, List<Integer> list){
    
19.         if(root == null) return;
    
20.         if(root != null){
    
21.             help(root.left,list);
    
22.             list.add(root.val);
    
23.             help(root.right,list);
    
24.         }
    
25.     }
    
26. }

复制代码

1. /**
   
2. * Definition for a binary tree node.
   
3. * public class TreeNode {
   
4. *     int val;
   
5. *     TreeNode left;
   
6. *     TreeNode right;
   
7. *     TreeNode(int x) { val = x; }
   
8. * }
   
9. */
   
10. class Solution {
    
11.     int kth = 0;
    
12.     int result = 0;
    
13.     public int kthSmallest(TreeNode root, int k) {
    
14.         kth = k;
    
15.         help(root);
    
16.         return result;
    
17.         
    
18.     }
    
19.     private void help(TreeNode root){
    
20.         if(root == null || kth == 0) return;
    
21.         
    
22.         help(root.left);
    
23.         kth--;
    
24.         if(kth == 0) result = root.val;
    
25.         help(root.right);
    
26.     }
    
27. }

复制代码