【LeetCode:2476. 二叉搜索树最近节点查询 + 中序遍历 + 有序表】

在这里插入图片描述

🚀 算法题 🚀

🌲 算法刷题专栏 | 面试必备算法 | 面试高频算法 🍀
🌲 越难的东西,越要努力坚持，因为它具有很高的价值，算法就是这样✨
🌲 作者简介：硕风和炜，CSDN-Java领域优质创作者🏆，保研|国家奖学金|高中学习JAVA|大学完善JAVA开发技术栈|面试刷题|面经八股文|经验分享|好用的网站工具分享💎💎💎
🌲 恭喜你发现一枚宝藏博主,赶快收入囊中吧🌻
🌲 人生如棋，我愿为卒，行动虽慢，可谁曾见我后退一步？🎯🎯

🚀 算法题 🚀

在这里插入图片描述

🍔 目录

- 🚩 题目链接
- ⛲ 题目描述
- 🌟 求解思路&实现代码&运行结果
- - ⚡ 中序遍历 + 有序表
  - - 🥦 求解思路
    - 🥦 实现代码
    - 🥦 运行结果
- 💬 共勉

🚩 题目链接

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

⛲ 题目描述

给你一个二叉搜索树的根节点 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, 105] 内
1 <= Node.val <= 106
n == queries.length
1 <= n <= 105
1 <= queries[i] <= 106

🌟 求解思路&实现代码&运行结果

⚡ 中序遍历 + 有序表

🥦 求解思路

该题目先通过中序遍历来找到一棵二叉树的顺序，然后遍历queries中的数字，通过有序表来找到大于某一个数字的最小值和小于某一个数的最大值。记录到每次的结果中，最终返回。
有了基本的思路，接下来我们就来通过代码来实现一下递归和迭代的解法。

🥦 实现代码

/**
 * Definition for a binary tree node.
 * public 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;
 * }
 * }
 */
class Solution {

    TreeMap<Integer, Integer> map = new TreeMap<>();

    public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {
        List<List<Integer>> ans = new ArrayList<>();
        if (root == null)
            return ans;
        dfs(root);
        map.put(-1, -1);
        for (int v : queries) {
            List<Integer> nums = new ArrayList<>();
            nums.add(map.floorKey(v) == null ? -1 : map.floorKey(v));
            nums.add(map.ceilingKey(v) == null ? -1 : map.ceilingKey(v));
            ans.add(nums);
        }
        return ans;
    }

    public void dfs(TreeNode root) {
        if (root == null)
            return;
        dfs(root.left);
        map.put(root.val, root.val);
        dfs(root.right);
    }

}