首页 > 代码库 > 272. Closest Binary Search Tree Value II

272. 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.

 

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

Hint:

  1. Consider implement these two helper functions:
    1. getPredecessor(N), which returns the next smaller node to N.
    2. getSuccessor(N), which returns the next larger node to N.
    Show More Hint 

 

Hide Company Tags
 Google
Hide Tags
 Tree Stack
Show Similar Problems
 用inorder来做 , bst inorder是有序的。
/** * Definition for a binary tree node. * public class TreeNode { *     int val; *     TreeNode left; *     TreeNode right; *     TreeNode(int x) { val = x; } * } */ //use inorder it will be a increase arraypublic class Solution {    public List<Integer> closestKValues(TreeNode root, double target, int k) {        List<Integer> res = new LinkedList<Integer>();        getClosestKValues(res, root, target, k);        return res;    }    public void getClosestKValues(List<Integer> res, TreeNode root, double target, int k){        if(root == null) return;        getClosestKValues(res, root.left, target, k);        if(res.size() == k){            if(Math.abs(res.get(0) - target) > Math.abs(root.val - target)){                res.remove(0);                res.add(root.val);            }            else                return;        }        else            res.add(root.val);        getClosestKValues(res, root.right, target, k);    }}

 

272. Closest Binary Search Tree Value II