leetcode刷题记录37-2476. 二叉搜索树最近节点查询

本文主要是介绍leetcode刷题记录37-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, 10^5] 内
• 1 <= Node.val <= 10^6
• n == queries.length
• 1 <= n <= 10^5
• 1 <= queries[i] <= 10^6

问题分析：

刚做完一看运行时间1966ms，击败了19.57%。心说完了，自己想出来的无脑解法果然废了。。。然后一看官解，好好好，官解剽窃我的思路是吧。

我的思路就是：首先题目给了一个二叉搜索树，我们直接中序遍历把树节点值全存一个数组arr里，易知这个数组有序，接着直接二分查找对应结点即可。

代码如下：

class Solution {
public:vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {vector<int> res;//    中序遍历存储有序数组function<void(TreeNode*)> inorder = [&](TreeNode* node) {if (node == nullptr)return;inorder(node->left);res.push_back(node->val);inorder(node->right);};inorder(root);//    结果数组vector<vector<int>> ans;for (int i = 0; i < queries.size(); ++i) {//    内置二分找大于等于元素，返回迭代器auto p = lower_bound(res.begin(), res.end(), queries[i]);//    如果找到了并且是对应元素本身if (p != res.end() && *p == queries[i]) {ans.push_back({*p, *p});//    否则push{lower,upper}} else {int lower = (p == res.begin()) ? -1 : *(p - 1);int upper = (p == res.end()) ? -1 : *p;ans.push_back({lower, upper});}}return ans;}
};

这篇关于leetcode刷题记录37-2476. 二叉搜索树最近节点查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---