Leetcode 2025-02-24 题目分享

有坑

二叉搜索树最近节点查询

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

1
2
3

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

思路

在搜索树中查找最大最小值问题，很容易让我们联想到使用搜索树的性质。

- 中序遍历结果是有序的

- 左子树所有节点值小于根节点值；右子树所有节点值大于根节点值
所以自然可以想到从上面两个性质出发去解决。
但第一种方法需要将树遍历一次，然后再写二分来查找。

我觉得麻烦，所以直接使用了第二种思路，得到如下代码。

具体就是按性质 2 遍历二叉搜索树：求出所有比目标值小的值中的最大值，以及比目标值大的值中的最小值。

function closestNodes(root: TreeNode | null, queries: number[]): number[][] {
    let ans:number[][] = [];
    // 寻找最大最小值
    const get = (val:number):number[] => {
        let minv = -1, maxv = 1e7;
        // dfs搜索
        const search = (node:TreeNode) => {
            let cur = node.val;
            // 小于等于待查询值：更新minv，让minv变大
            if (cur <= val) minv = Math.max(minv, cur);
            // 大于等于待查询值：更新maxv，让maxv变小
            if (cur >= val) maxv = Math.min(maxv, cur);
            if (cur > val && node.left != null) search(node.left);
            else if (cur < val && node.right != null) search(node.right);
            else return;
        };
        search(root!);
        return [minv, maxv==1e7?-1:maxv];
    };
    for (let q of queries) ans.push(get(q));
    return ans;
};

看似复杂度是 O(n * log n)，但这是要求搜索树是平衡条件下！。

对于一个不平衡的树，例如树退化为一条链。

我们每次遍历仍需要遍历每一个节点，是 O(n)时间。

只有在平衡的时候，每一次遍历才能节省一半的搜索数量！
正解就是用二分 🙌

function closestNodes(root: TreeNode | null, queries: number[]): number[][] {
    let ans:number[][] = [], arr:number[] = [];
    // 搞成有序数组
    const dfs = (root:TreeNode | null) => {
        if (root == null) return;
        dfs(root!.left);
        arr.push(root!.val);
        dfs(root!.right);
    };
    // 二分查找
    const get = (val:number):number[] => {
        let l = 0, r = arr.length-1;
        while (l <= r){
            let mid = l+r >> 1;
            if (arr[mid] <= val) l = mid+1;
            else r = mid-1;
        }
        // 注意边界值 arr[r]代表小于val的最大值
        if (r == -1) return [-1, arr[0]];
        if (arr[r] == val) return [val, val];
        return [arr[r], r==arr.length-1?-1:arr[r+1]];
    };
    dfs(root);
    for (let q of queries) ans.push(get(q));
    return ans;
};

复杂度分析

时间：O(n * log n)。
空间：O(n)。