​LeetCode解法汇总2476. 二叉搜索树最近节点查询

本文主要是介绍​LeetCode解法汇总2476. 二叉搜索树最近节点查询，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

 目录链接：

力扣编程题-解法汇总_分享+记录-CSDN博客

GitHub同步刷题项目：

GitHub - September26/java-algorithms: 算法题汇总，包含牛客，leetCode，lintCode等网站题目的解法和代码，以及完整的mode类，甚至链表代码生成工具都有提供。

原题链接：. - 力扣（LeetCode）

描述：

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

解题思路：

这道题，其实可以分成寻找小于等于target的数中最大的，以及大于等于target的数中最小的。

寻找小于等于target的数中最大的数值，属于典型的二叉树搜索，构建一个方法searchValue进行二叉树递归遍历。

传入参数1:TreeNode root，代表当前遍历的节点

传入参数2:int lastValue，代表上一次匹配到的最合适的值，

传入参数3:int target，代表目标值。

方法中，如果节点值等于目标值，则直接返回当前值即可。

如果节点值大于目标值，则递归搜索其左子树，因为只有左子树的值才会比目标值小，最合适的值仍然为上一次的，因为这一次的不满足。

如果节点值小于目标值，则递归搜索其左子树，因为只有右子树的值才会比目标值大，最合适的值调整为当前值，因为本地的值符合匹配。

寻找大于等于target的数中最小的方法也是一样。

代码：

方法1:

class Solution2476
{
public:vector<vector<int>> closestNodes(TreeNode *root, vector<int> &queries){vector<vector<int>> list;for (int i : queries){int i1 = searchValue(root, true, -1, i);int i2 = searchValue(root, false, -1, i);vector<int> vec = {i1, i2};list.push_back(vec);}return list;}// 寻找比target小但最接近target的值int searchValue(TreeNode *root, bool isSmall, int lastValue, int target){if (root == nullptr){return lastValue;}int val = root->val;if (val == target){return val;}if (val > target){return searchValue(root->left, isSmall, isSmall ? lastValue : val, target);}return searchValue(root->right, isSmall, isSmall ? val : lastValue, target);}
};

方法2:

class Solution2476
{
public:vector<vector<int>> closestNodes(TreeNode *root, vector<int> &queries){vector<int> sortList;vector<TreeNode *> list;search(root, sortList);vector<vector<int>> res;for (int i = 0; i < queries.size(); i++){int target = queries[i];int left = -1, right = -1;auto it = lower_bound(sortList.begin(), sortList.end(), target);if (it != sortList.end()){right = *it;if (*it == target){left = *it;res.push_back({left, right});continue;}}if (it != sortList.begin()){left = *(--it);}res.push_back({left, right});}return res;}// 寻找比target小但最接近target的值void search(TreeNode *node, vector<int> &sortList){if (node == nullptr)return;search(node->left, sortList);sortList.push_back(node->val);search(node->right, sortList);}
};

这篇关于​LeetCode解法汇总2476. 二叉搜索树最近节点查询的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---