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.
Solution 1: use in-order traversal and counter the kth number.
public class Solution {
public int kthSmallest(TreeNode root, int k) {
Deque<TreeNode> stack=new LinkedList<>();
TreeNode x=root;
while (x!=null || !stack.isEmpty()) {
if (x!=null) {
stack.push(x);
x=x.left;
}
else {
x=stack.pop();
if (--k==0) return x.val;
x=x.right;
}
}
return 0;
}
}
没有评论:
发表评论