题目：

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

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

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

返回数组 answer 。

1
2
3

输入：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] 。

解题思路：

模拟

会超时，最后一个测试用例的二叉搜索树是偏移树，时间复杂度会从O(logn)涨到O(n)

二叉树中序遍历 + 二分查找

因为二叉搜索树的节点结构为左子节点小于当前节点，右子节点大于当前节点

我们使用中序遍历可以得到一个已经排序的数组。

然后使用二分查找查找最大值和最小值，题目中的min 和 max 就是我们二分查找的判断条件。

如果使用Python语言可以使用bisect库

使用C++只能自己写

代码：

Python

class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        a = []
        def dfs(o):
            if o is None: return
            dfs(o.left)
            a.append(o.val)
            dfs(o.right)
        dfs(root)

        ans = [[-1, -1] for _ in range(len(queries))]
        for i, q in enumerate(queries):
            j = bisect_right(a, q) - 1
            min = a[j] if j >= 0 else -1
            j = bisect_left(a, q)
            max = a[j] if j < len(a) else -1
            ans[i] = [min, max]
        
        return ans

C++

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<int> a;
        dfs(root, a);
        
        vector<vector<int>> ans;
        for (auto &x: queries) {
            int j = bisect_right(a, x);
            int min, max;
            if (j >= 0)
            {
                min = a[j];
            }
            else
            {
                min = -1;
            }

            j = bisect_left(a, x);
            if (j < a.size())
            {
                max = a[j];
            }
            else
            {
                max = -1;
            }

            vector<int> i;
            i.push_back(min);
            i.push_back(max);
            ans.push_back(i);
        }
        return ans;
    }
    
    void dfs(TreeNode* o, vector<int> &a) {
        if (o == nullptr) return;
        dfs(o->left, a);
        a.push_back(o->val);
        dfs(o->right, a);
    }

    int bisect_left(vector<int> &a, int num) {
        int l = 0, r = a.size();
        while (l < r) {
            int mid = (r - l >> 1) + l;
            if (a[mid] >= num)
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l;
    }

    int bisect_right(vector<int> &a, int num) {
        int l = 0, r = a.size();
        while (l < r) {
            int mid = (r - l >> 1) + l;
            if (num < a[mid])
            {
                r = mid;
            }
            else
            {
                l = mid + 1;
            }
        }
        return l - 1;
    }
};