Skip to content

Closest Binary Search Tree Value II (tricky)

Tim_Gao edited this page Sep 18, 2016 · 1 revision
  1. 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;
    }
}

Clone this wiki locally