270. 最接近的二叉搜索树值

方案一、使用BFS或者DFS遍历每个元素，可直接获得结果

 1 public int closestValue(TreeNode root, double target) {
 2         int tag=root.val;
 3         double res= Math.abs(root.val-target);
 4         Deque<TreeNode> queue = new LinkedList<TreeNode>();
 5         queue.add(root);
 6         while(!queue.isEmpty()){
 7             TreeNode temp = queue.poll();
 8             double diff = Math.abs(temp.val-target);
 9             if(diff<res){
10                 res=diff;
11                 tag=temp.val;
12             }
13             if(temp.left!=null){
14                 queue.add(temp.left);
15             }
16             if(temp.right!=null){
17                 queue.add(temp.right);
18             }
19         }
20         return tag;
21     }

方案二、使用二分查找

题目给定了二叉搜索树，这个情况下整棵树的节点是存在左孩子<父节点<右孩子这样的关系的

因此我们可以模仿二分查找，垂直向下查找，而不用遍历每个元素

 1 public int closestValue(TreeNode root, double target) {
 2         int closest=root.val;
 3         TreeNode tag = root;
 4         while(tag!=null){
 5             // 比较当前节点与目标值的差
 6             closest = Math.abs(tag.val-target) < Math.abs(closest-target) ? tag.val:closest;
 7             // 二分查找向下遍历
 8             tag= tag.val < target ? tag.right:tag.left;
 9         }
10         return closest;
11     }

争取早日不再是一只菜鸡