2476.二叉搜索树最近节点查询

目标

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

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

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

返回数组 answer 。

说明：

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

思路

这个题目求的是最接近给定值的节点值。一个朴素的想法是将搜索树的值都列出来，然后从中查找前后的值。这里列出值无需保留树的结构，虽然节点数目范围是[2,10^5]，但如果考虑一个极端的情况，树的深度就是10^5-1，保留树的结构就大约需要2^(10^5)约等于10^3010个元素。二叉搜索树如果采用中序遍历结果就是正序的。但是考虑到存在null值，数组可能填不满，这样就破坏了有序性。想要使用二分查找还要先排序。Arrays.binarySearch 的结果如果找到相应的值则返回对应的index>=0。如果没有找到，则返回-insertion point-1。所谓插入点，其前一个位置的值小于搜索的值。例如 arr = [2, 3, 4, 5, 6, 7, 9] 搜索值为8，使用二分查找则返回 -6-1，arr[5]的值是7，8应该插入到7后面，即插入点为6。因此，如果没查询到，可以使用-index-1得到最近的大于搜索值的位置，这里需要注意数组的边界。

代码

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @date 2024-02-24 18:57
 */
public class ClosestNodes {
    public static 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;
        }

        @Override
        public String toString() {
            return "TreeNode{" +
                    "val=" + val +
                    ", left=" + left +
                    ", right=" + right +
                    '}';
        }
    }

    public final int MAX = 100000;
    public int[] values = new int[MAX];
    public int i = 0;

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        Arrays.fill(values, -1);
        traverseSubTree(root);
        // 遍历之后values并非全部有序，因为存在null节点，没初始化 值为0
        Arrays.sort(values);
        List<List<Integer>> res = new ArrayList<>(queries.size());
        for (Integer query : queries) {
            List<Integer> tmp = new ArrayList<>(2);
            int ri = Arrays.binarySearch(values, query);
            if (ri < 0) {
                ri = -ri - 1;
                if (ri == values.length) {
                    tmp.add(values[values.length -1]);
                    tmp.add(-1);
                } else if(ri == 0){
                    tmp.add(-1);
                    tmp.add(values[0]);
                } else {
                    tmp.add(values[ri - 1]);
                    tmp.add(values[ri]);
                }
            } else {
                // 如果存在
                tmp.add(values[ri]);
                tmp.add(values[ri]);
            }
            res.add(tmp);
        }
        return res;
    }

    public void traverseSubTree(TreeNode subTree) {
        if (subTree.left != null) {
            traverseSubTree(subTree.left);
        }
        values[i++] = subTree.val;
        if (subTree.right != null) {
            traverseSubTree(subTree.right);
        }
    }
}

性能