# 2476. Closest Nodes Queries in a Binary Search Tree
###### tags: `Leetcode` `Medium` `Tree` `Binary Search` `Binary Search Tree` `Inorder Traversal`
Link: https://leetcode.com/problems/closest-nodes-queries-in-a-binary-search-tree/description/
## 思路
先inorder traversal 把所有nums按顺序放进list里面 时间复杂度为O(N)
然后做binary search 对于每一个query 时间复杂度为O(logN)
这里不知道这个tree是不是balanced 所以worse case search tree需要O(N) 因此为了降低时间复杂度 我们先做inorder traversal
如果这个tree是balanced binary search tree 那么每一次search tree都是O(logN) 那么就不需要先做一遍inorder traversal
## Code

class Solution {
    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<Integer> nums = new ArrayList<>();
        inorderTraversal(root, nums);
        int n = nums.size();
        List<List<Integer>> ans = new ArrayList<>();
        for(int q:queries){
            int l=0, r=n;
            while(l<r){
                int mid = l+(r-l)/2;
                if(nums.get(mid)<q) l = mid+1;
                else r = mid;
            }
            List<Integer> tmp = new ArrayList<>();
            if(l==n){
                tmp.add(nums.get(l-1));
                tmp.add(-1);
            }
            else if(nums.get(l)==q){
                tmp.add(q);
                tmp.add(q);
            }
            else if(l==0){
                tmp.add(-1);
                tmp.add(nums.get(l));
            }
            else{
                tmp.add(nums.get(l-1));
                tmp.add(nums.get(l));
            }
            ans.add(tmp);
        }
        return ans;
    }
    public void inorderTraversal(TreeNode root, List<Integer> nums){
        if(root==null) return;
        inorderTraversal(root.left, nums);
        nums.add(root.val);
        inorderTraversal(root.right, nums);
    }
}