题目链接：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); } }
