Medium

题目描述

给你一个二叉搜索树的根节点 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] 。

提示：

  • 树中节点的数目在范围 [2, 10^5] 内
  • 1 <= Node.val <= 10^6
  • n == queries.length
  • 1 <= n <= 10^5
  • 1 <= queries[i] <= 10^6

解题思路

这道题的核心思路是利用二叉搜索树的性质，通过中序遍历得到有序数组，然后对每个查询进行二分查找。

思路分析：

  1. 预处理阶段：对二叉搜索树进行中序遍历，得到一个递增的有序数组。这是关键步骤，因为BST的中序遍历天然就是有序的。

  2. 查询处理：对于每个查询值，我们需要找到：

    • mini：小于等于查询值的最大元素
    • maxi：大于等于查询值的最小元素

  3. 二分查找优化：在有序数组中，我们可以使用二分查找来高效地找到目标位置：

    • 使用 lower_bound 找到第一个大于等于查询值的位置
    • 根据这个位置来确定 mini 和 maxi 的值

具体实现细节：

  • 如果找到的位置指向的值等于查询值，那么 mini 和 maxi 都是这个值
  • 如果找到的位置是第一个大于查询值的位置，那么 maxi 就是这个值，mini 是前一个值
  • 需要处理边界情况：位置在数组开头或结尾时的特殊处理

时间复杂度：O(n + q log n)，其中 n 是树中节点数，q 是查询数。空间复杂度：O(n)。

推荐解法：中序遍历 + 二分查找，这是最优解法。

代码实现

class Solution {
public:
    vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {
        vector<int> vals;
        
        // 中序遍历获取有序数组
        function<void(TreeNode*)> inorder = [&](TreeNode* node) {
            if (!node) return;
            inorder(node->left);
            vals.push_back(node->val);
            inorder(node->right);
        };
        
        inorder(root);
        
        vector<vector<int>> result;
        
        for (int query : queries) {
            int mini = -1, maxi = -1;
            
            // 使用lower_bound找到第一个大于等于query的位置
            auto it = lower_bound(vals.begin(), vals.end(), query);
            
            // 找maxi：第一个大于等于query的值
            if (it != vals.end()) {
                maxi = *it;
            }
            
            // 找mini：最大的小于等于query的值
            if (it != vals.begin()) {
                mini = *(it - 1);
            }
            
            // 如果找到的值正好等于query，那么mini也是这个值
            if (it != vals.end() && *it == query) {
                mini = query;
            }
            
            result.push_back({mini, maxi});
        }
        
        return result;
    }
};

class Solution:
    def closestNodes(self, root: Optional[TreeNode], queries: List[int]) -> List[List[int]]:
        # 中序遍历获取有序数组
        vals = []
        
        def inorder(node):
            if not node:
                return
            inorder(node.left)
            vals.append(node.val)
            inorder(node.right)
        
        inorder(root)
        
        result = []
        
        for query in queries:
            mini, maxi = -1, -1
            
            # 使用bisect_left找到第一个大于等于query的位置
            pos = bisect.bisect_left(vals, query)
            
            # 找maxi：第一个大于等于query的值
            if pos < len(vals):
                maxi = vals[pos]
            
            # 找mini：最大的小于等于query的值
            if pos > 0:
                mini = vals[pos - 1]
            
            # 如果找到的值正好等于query，那么mini也是这个值
            if pos < len(vals) and vals[pos] == query:
                mini = query
            
            result.append([mini, maxi])
        
        return result

public class Solution {
    public IList<IList<int>> ClosestNodes(TreeNode root, IList<int> queries) {
        List<int> vals = new List<int>();
        
        // 中序遍历获取有序数组
        void Inorder(TreeNode node) {
            if (node == null) return;
            Inorder(node.left);
            vals.Add(node.val);
            Inorder(node.right);
        }
        
        Inorder(root);
        
        IList<IList<int>> result = new List<IList<int>>();
        
        foreach (int query in queries) {
            int mini = -1, maxi = -1;
            
            // 使用BinarySearch找到位置
            int pos = vals.BinarySearch(query);
            if (pos < 0) {
                pos = ~pos; // 转换为插入位置
            }
            
            // 找maxi：第一个大于等于query的值
            if (pos < vals.Count) {
                maxi = vals[pos];
            }
            
            // 找mini：最大的小于等于query的值
            if (pos > 0) {
                mini = vals[pos - 1];
            }
            
            // 如果找到的值正好等于query，那么mini也是这个值
            if (pos < vals.Count && vals[pos] == query) {
                mini = query;
            }
            
            result.Add(new List<int> { mini, maxi });
        }
        
        return result;
    }
}

var closestNodes = function(root, queries) {
    const vals = [];
    
    // 中序遍历获取有序数组
    function inorder(node) {
        if (!node) return;
        inorder(node.left);
        vals.push(node.val);
        inorder(node.right);
    }
    
    inorder(root);
    
    const result = [];
    
    for (const query of queries) {
        let mini = -1, maxi = -1;
        
        // 二分查找第一个大于等于query的位置
        let left = 0, right = vals.length;
        while (left < right) {
            const mid = Math.floor((left + right) / 2);
            if (vals[mid] < query) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        
        const pos = left;
        
        // 找maxi：第一个大于等于query的值
        if (pos < vals.length) {
            maxi = vals[pos];
        }
        
        // 找mini：最大的小于等于query的值
        if (pos > 0) {
            mini = vals[pos - 1];
        }
        
        // 如果找到的值正好等于query，那么mini也是这个值
        if (pos < vals.length && vals[pos]
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n + q log n)n为树节点数，q为查询数。中序遍历O(n)，每次查询二分查找O(log n)
空间复杂度O(n)存储中序遍历结果的数组空间

相关题目