Closest Binary Search Tree Value I

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

Note: Given target value is a floating point. You are guaranteed to have only one unique value in the BST that is closest to the target.

递归法

复杂度

时间 O(logN) 空间 O(H)

思路

根据二叉树的性质，我们知道当遍历到某个根节点时，最近的那个节点要么是在子树里面，要么就是根节点本身。所以我们根据这个递归，返回子树中最近的节点，和根节点中更近的那个就行了。

代码

public class Solution {    public int closestValue(TreeNode root, double target) {        // 选出子树的根节点        TreeNode kid = target < root.val ? root.left : root.right;        // 如果没有子树，也就是递归到底时，直接返回当前节点值        if(kid == null) return root.val;        // 找出子树中最近的那个节点        int closest = closestValue(kid, target);        // 返回根节点和子树最近节点中，更近的那个节点        return Math.abs(root.val - target) < Math.abs(closest - target) ? root.val : closest;    }}

迭代法

复杂度

时间 O(logN) 空间 O(H)

思路

记录一个最近的值，然后沿着二叉搜索的路径一路比较下去，并更新这个最近值就行了。因为我们知道离目标数最接近的数肯定在二叉搜索的路径上。

代码

public class Solution {    public int closestValue(TreeNode root, double target) {        int closest = root.val;        while(root != null){// 如果该节点的离目标更近，则更新到目前为止的最近值closest = Math.abs(closest - target) < Math.abs(root.val - target) ? closest : root.val;// 二叉搜索root = target < root.val ? root.left : root.right;        }        return closest;    }}

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:

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

中序遍历法

复杂度

时间 O(N) 空间 Max(O(K),O(H))

思路

二叉搜索树的中序遍历就是顺序输出二叉搜索树，所以我们只要中序遍历二叉搜索树，同时维护一个大小为K的队列，前K个数直接加入队列，之后每来一个新的数（较大的数），如果该数和目标的差，相比于队头的数离目标的差来说，更小，则将队头拿出来，将新数加入队列。如果该数的差更大，则直接退出并返回这个队列，因为后面的数更大，差值也只会更大。

代码

public class Solution {    public List<Integer> closestKValues(TreeNode root, double target, int k) {        Queue<Integer> klist = new LinkedList<Integer>();        Stack<TreeNode> stk = new Stack<TreeNode>();        // 迭代中序遍历二叉搜索树的代码        while(root != null){stk.push(root);root = root.left;        }        while(!stk.isEmpty()){TreeNode curr = stk.pop();// 维护一个大小为k的队列// 队列不到k时直接加入if(klist.size() < k){    klist.offer(curr.val);} else {// 队列到k时，判断下新的数是否更近，更近就加入队列并去掉队头    int first = klist.peek();    if(Math.abs(first - target) > Math.abs(curr.val - target)){        klist.poll();        klist.offer(curr.val);    } else {    // 如果不是更近则直接退出，后面的数只会更大        break;    }}// 中序遍历的代码if(curr.right != null){    curr = curr.right;    while(curr != null){        stk.push(curr);        curr = curr.left;    }}        }        // 强制转换成List，是用LinkedList实现的所以可以转换        return (List<Integer>)klist;    }}