题目链接：2476. 二叉搜索树最近节点查询（中等）
算法原理：
这题其实就是对模板的再次应用罢了👇
优选算法-二分：18.在排序数组中查找元素的第一个和最后一个位置
解法一：二分查找+层序遍历
133ms击败5.17%
时间复杂度O(Nlogn)
整体思路很简单👇
①通过层序遍历将树中的节点值提取出来
②排序后通过二分查找依次查找queries中每个数在树中的mini、maxi
具体思考过程
①在层序遍历的同时将树中的节点值摘到一个顺序表中
②由于需要给对应的queries找数，找数要是一次遍历要O(N)的时间复杂度，但是用二分查找只需要O(logN)的时间复杂度，且找的数恰好是queries的最左右端点模型找到的数，所以优先选择二分查找
③使用二分查找需要有序的前提，因此需要对顺序表排序
④层序遍历方法可参考下面的博客👇
Java数据结构——7.二叉树《干货笔记》
解法二：二分查找+中序遍历
117ms击败14.28%
时间复杂度O(Nlogn)
其实就是提取节点值的方法变了，层序遍历需要创建队列，类似BFS，咱们也可改成类似DFS的前序遍历、中序遍历、后序遍历
Java代码：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//解法一：二分查找+层序遍历
List<Integer> list=new ArrayList<>();
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<List<Integer>> ret=new ArrayList<>();
//将树中的节点全部提取出来
bfs(root);
Collections.sort(list);
for(int x:queries){
List<Integer> tmp=new ArrayList<>();
//求最右端点模型找mini
int left=0,right=list.size()-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(list.get(mid)>x) right=mid-1;
else left=mid;
}
//如果所有数都比x大，就添加-1进去
if(list.get(left)>x) tmp.add(-1);
else tmp.add(list.get(left));
//求最左端点模型找maxi
left=0;right=list.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(list.get(mid)<x) left=mid+1;
else right=mid;
}
//如果所有数都比x小，就添加-1进去
if(list.get(left)<x) tmp.add(-1);
else tmp.add(list.get(left));
ret.add(tmp);
}
return ret;
}
//层序遍历提取节点值
private void bfs(TreeNode node){
if(node==null) return;
Queue<TreeNode> q=new LinkedList<>();
q.add(node);
while(!q.isEmpty()){
TreeNode cur=q.poll();
list.add(cur.val);
if(cur.left!=null) q.offer(cur.left);
if(cur.right!=null) q.offer(cur.right);
}
}
}
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
//解法二：二分查找+中序遍历
List<Integer> list=new ArrayList<>();
public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
List<List<Integer>> ret=new ArrayList<>();
//将树中的节点全部提取出来
dfs(root);
Collections.sort(list);
for(int x:queries){
List<Integer> tmp=new ArrayList<>();
//求最右端点模型找mini
int left=0,right=list.size()-1;
while(left<right){
int mid=left+(right-left+1)/2;
if(list.get(mid)>x) right=mid-1;
else left=mid;
}
//如果所有数都比x大，就添加-1进去
if(list.get(left)>x) tmp.add(-1);
else tmp.add(list.get(left));
//求最左端点模型找maxi
left=0;right=list.size()-1;
while(left<right){
int mid=left+(right-left)/2;
if(list.get(mid)<x) left=mid+1;
else right=mid;
}
//如果所有数都比x小，就添加-1进去
if(list.get(left)<x) tmp.add(-1);
else tmp.add(list.get(left));
ret.add(tmp);
}
return ret;
}
//中序遍历提取节点值
private void dfs(TreeNode node){
if(node==null) return ;
dfs(node.left);
list.add(node.val);
dfs(node.right);
}
}
