问题描述

给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。

请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [mini, maxi] ：

• mini 是树中小于等于 queries[i] 的 最大值 。如果不存在这样的值，则使用 -1 代替。
• maxi 是树中大于等于 queries[i] 的 最小值 。如果不存在这样的值，则使用 -1 代替。

返回数组 answer 。

示例 1 ：

输入：root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
输出：[[2,2],[4,6],[15,-1]]
解释：按下面的描述找出并返回查询的答案：
- 树中小于等于 2 的最大值是 2 ，且大于等于 2 的最小值也是 2 。所以第一个查询的答案是 [2,2] 。
- 树中小于等于 5 的最大值是 4 ，且大于等于 5 的最小值是 6 。所以第二个查询的答案是 [4,6] 。
- 树中小于等于 16 的最大值是 15 ，且大于等于 16 的最小值不存在。所以第三个查询的答案是 [15,-1] 。

示例 2 ：

输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 

解答思路 

 首先先观察本题，本题需要我们找到给出数组中的数在树中的前后数，数也可以是其本身，如果树中有的话，所以这其实就是一个搜索的问题，我们需要找到这个数，如果树中有这个数那我们就可以直接得到两个值，而如果不可以那么就搜索返回和这个数相差最小的数的位置。于是就转变成一个二分搜索的题目，因为二分需要我们得到有序的序列，而这个数又正好是一个二叉搜索树也就是二叉排序树，所以我们首先中序遍历一下这个树，得到有序数列之后，对给出的数组进行遍历查找，然后加入List进行返回即可。

代码如下

class Solution {public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {List<Integer> list=new ArrayList<>();List<List<Integer>> lists=new ArrayList<>();dfs(root,list);int n=list.size();int[] nums=new int[n];for(int i=0;i<n;i++)//经过测试直接访问数组这样更快nums[i]=list.get(i);for(int i:queries){List<Integer> l=new ArrayList<>();int j=search(nums,i);if(j<0){//如果搜索到<0,说明没有比这个更小的数据l.add(-1);l.add(nums[0]);}else if(j>=n){//如果搜索到>n-1，说明没有比这个更大的数据l.add(nums[n-1]);l.add(-1);}else{if(nums[j]==i){l.add(i);l.add(i);}else if(nums[j]>i){//进行分类if(j==0)l.add(-1);elsel.add(nums[j-1]);l.add(nums[j]);}else {l.add(nums[j]);if(j==n-1)l.add(-1);else    l.add(nums[j+1]);}}lists.add(l);}return lists;}public int search(int[] nums,int k){int l=0,r=nums.length-1;while(l<=r){int m=(l+r)/2;if(nums[m]==k)return m;else if(nums[m]>k)r=m-1;elsel=m+1;}return l;}public void dfs(TreeNode p,List<Integer> list){if(p!=null){dfs(p.left,list);list.add(p.val);dfs(p.right,list);}}
}