Closest Binary Search Tree Value II

Given a non-empty binary search tree and a target value, find k values in the BST that are closest to the target.

Note:

• Given target value is a floating point.

• You may assume k is always valid, that is: k ≤ total nodes.

• You are guaranteed to have only one unique set of k values in the BST that are closest to the target.

Example:

Input: root = [4,2,5,1,3], target = 3.714286, and k = 2

    4
   / \
  2   5
 / \
1   3

Output: [4,3]

Follow up: Assume that the BST is balanced, could you solve it in less than O(n) runtime (where n = total nodes)?

O(N)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        
        
        if(root == null)
            return res;
        
        Stack<TreeNode> stack = new Stack<>();
        
        TreeNode cur = root;
        
        while(!stack.isEmpty() || cur != null){
            while(cur != null){
                stack.push(cur);
                cur = cur.left;
            }
            
            cur = stack.pop();
            if(res.size() < k){
                res.add(cur.val);
            }else{
                if(Math.abs(cur.val - target) < Math.abs(res.get(0) - target)){
                    res.add(cur.val);
                    res.remove(0);
                }
            }
            
            cur = cur.right;
        }
        
        return res;
        
    }
    
}

利用找到比target 小的，和比target大的数，时间复杂度o(klongN)

整体思路是把target cast到整形，找到第一个比target小的节点值，第一个比target大的节点值，根据绝对值来决定选择哪个，大的放到deque尾部，小的放到deque头部，把加入deque的那个节点 继续调用相应的方法 往两端扩散，比target大的节点就找一个再大一点的，比target小的节点 就找一个比他再小一点的节点

在找floor时，是找比target第一个小的数，当遇到节点比target小的时候，这个时候递归往右走一下，尝试寻找比当前节点大，比target小的数，如果存在，那么这个数与target的绝对值肯定比当前节点的数与target的绝对值小，如果返回空的话，说明当前节点是距离target最近的最小节点

同理，在找ceiling时，是找比target大的第一个数，当遇到节点小于target时，自然的往右走，不用特殊处理，当遇到节点大于target时，递归尝试往左走，试着找出一个比当前节点小，比target大的值，如果返回null，说明不存在，就返回当前节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
       
        Deque<Integer> deque = new LinkedList<>();
        
        TreeNode floor = getFloor(root, (int)target);
        TreeNode ceiling = getCeiling(root,(int) target + 1);
        
        while(deque.size() < k && !(floor == null && ceiling == null)){
            if(floor == null || ceiling != null && Math.abs(floor.val - target) > Math.abs(ceiling.val - target)){
                deque.offerLast(ceiling.val);
                ceiling = getCeiling(root,ceiling.val+1);
            }else{
                deque.offerFirst(floor.val);
                floor = getFloor(root, floor.val-1);
            }
        }
        
        return new ArrayList<>(deque);
        
    }
    
    public TreeNode getFloor(TreeNode node, int target){
         if(node == null) {
            return null;
        }
        if(target == node.val) {
            return node;
        } else if(target < node.val) {
            return getFloor(node.left, target);
        } else {
            TreeNode n = getFloor(node.right, target);
            return n == null ? node : n;
        }
            
    }
    
     public TreeNode getCeiling(TreeNode node, int target){
         if(node == null) {
            return null;
        }
        if(target == node.val) {
            return node;
        } else if(target > node.val) {
            return getCeiling(node.right, target);
        } else {
            TreeNode n = getCeiling(node.left, target);
            return n == null ? node : n;
        }
            
    }
    
}

时间复杂度 o(k+logn)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        List<Integer> res = new ArrayList<>();
        
        if(root == null)
            return res;
        
        Stack<TreeNode> larger = new Stack<>();
        
        Stack<TreeNode> smaller = new Stack<>();
        
        TreeNode cur = root;
        
        while(cur != null){
            if(cur.val < target){
                smaller.push(cur);
                cur = cur.right;
            }else{
                larger.push(cur);
                cur = cur.left;
            }
        }
        
        while(res.size() < k ){
            double diffs = smaller.isEmpty()? Long.MAX_VALUE : Math.abs(smaller.peek().val - target);
            double diffl = larger.isEmpty() ? Long.MAX_VALUE : Math.abs(larger.peek().val-target);
            
            if(diffs < diffl){
                res.add(smaller.peek().val);
                getPrev(smaller);
            }else{
                res.add(larger.peek().val);
                getNext(larger);
            }
        }
        
        return res;
    }
    
    public void getPrev(Stack<TreeNode> stack){
        TreeNode node = stack.pop();
        
        TreeNode cur = node.left;
        
        while(cur != null){
            stack.push(cur);
            cur  = cur.right;
        }
    }
    
    public void getNext(Stack<TreeNode> stack){
        TreeNode node = stack.pop();
        
        TreeNode cur = node.right;
        
        while(cur  != null){
            stack.push(cur);
            cur = cur.left;
        }
    }
}

优化 时间复杂度 o(k+logn),空间复杂度 o(logN)

use two stack to save the treenode, one stack is for treenode val smaller than target, other one is for treenode val larger or equal with target, . then if the res.size < k, just get peek of the two stack, to compare the distance, after select one, update the stack. for example, I picked the stack from the smaller value stack, then I go to the stack.pop node's right, which is larger than the picked node. Then go to the node's left, this is trying to find the fist node larger than the peek(). same with larger stack.

为什么一开始push到stack以后 后面还要push？

因为一开始push的时候，只是围绕target值，对树进行二分查找，随着后面往res里放结果，需要已target的值为中心，往两边扩展塞进stack里备选，大的就找比他再大一点的，小的就找比他再小一点的，这些值在一开始都没有被压进stack

坑，当stack为空时，diff应该是Long.MAX_VALUE, 不然[0] Integer.MAX_VALUE, 1这个case会报异常

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public List<Integer> closestKValues(TreeNode root, double target, int k) {
        if(root == null )
            return null;
        
        Stack<TreeNode> prev = new Stack<>();
        Stack<TreeNode> next = new Stack<>();
        
        TreeNode cur = root;
        
        while(cur != null){
            if(cur.val < target){
                prev.push(cur);
                cur = cur.right;
            }else{
                next.push(cur);
                cur = cur.left;
            }
        }
        
        
        List<Integer> res = new ArrayList<>();
        
        while(res.size() < k){
            double diffP = prev.isEmpty() ? Long.MAX_VALUE : Math.abs(prev.peek().val - target);
            double diffN = next.isEmpty() ? Long.MAX_VALUE : Math.abs(next.peek().val-target);
            
            if(diffP < diffN){
                res.add(prev.peek().val);
                //找比现在这个小的
                getPrev(prev);
            }else{
                res.add(next.peek().val);
                //找比现在这个大的
                getNext(next);
            }
            
        }
        
        return res;
    }
    
    public void getPrev(Stack<TreeNode> prev){
        TreeNode node = prev.pop().left;
        
        while(node != null){
            prev.push(node);
            node = node.right;
        }
    }
    
    public void getNext(Stack<TreeNode> next){
        TreeNode node = next.pop().right;
        //node比现在的node要大，循环里找的是比node小的
        while(node != null){
            next.push(node);
            node =  node.left;
        }
    }
}