-
Notifications
You must be signed in to change notification settings - Fork 0
Closest Binary Search Tree Value II (tricky)
Tim_Gao edited this page Sep 18, 2016
·
1 revision
- mistake: forgot to push crt onto successor when find the node that is closest to target
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public List<Integer> closestKValues(TreeNode root, double target, int k) {
ArrayList<Integer> res = new ArrayList<>();
if (k < 1){
return res;
}
Stack<TreeNode> successor = new Stack<>();
Stack<TreeNode> predecessor = new Stack<>();
Double prev = null;
TreeNode crt = root;
while(crt != null || !successor.isEmpty()){
while(crt!=null){
successor.push(crt);
crt = crt.left;
}
crt = successor.pop();
if (prev != null){
if(Math.abs(target-prev) < Math.abs(target-crt.val)){
//This is the key, when find the diff starts growing, push crt back to successor!!!!
successor.push(crt);
break;
}
}
predecessor.push(crt);
prev = (double) crt.val;
crt = crt.right;
}
res.add(predecessor.pop().val);
--k;
TreeNode pred = null, succ = null;
while (k>0){
if (pred ==null && !predecessor.isEmpty()){
pred = predecessor.pop();
}
if (succ== null && !successor.isEmpty()){
succ = successor.pop();
}
if ( pred == null){
res.add(succ.val);
succ = succ.right;
while(succ!=null){
successor.push(succ);
succ= succ.left;
}
} else if(succ == null){
res.add(pred.val);
pred = null;
} else {
if (Math.abs(succ.val-target) < Math.abs(pred.val-target)){
res.add(succ.val);
succ = succ.right;
while(succ!=null){
successor.push(succ);
succ=succ.left;
}
} else {
res.add(pred.val);
pred = null;
}
}
--k;
}
return res;
}
}