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.
Example 1:
Input: root = [3,1,4,null,2], k = 1 3 / \ 1 4 \ 2 Output: 1
public int kthSmallest(TreeNode root, int k) {
ArrayList<Integer> inorderList = inoder(root, new ArrayList<Integer>());
return inorderList.get(k-1);
}
private ArrayList<Integer> inoder(TreeNode T, ArrayList<Integer> inorderList) {
if(T!=null) {
inoder(T.left, inorderList);
inorderList.add(T.val);
inoder(T.right, inorderList);
}
return inorderList;
}
No comments:
Post a Comment