微网站怎么做微名片,湖北省城乡和住房建设厅网站,服装网站建设运营规划,环江住房和城乡建设部网站目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
GitHub - September26/java-algorithms: 算法题汇总#xff0c;包含牛客#xff0c;leetCode#xff0c;lintCode等网站题目的解法和代码#xff0c;以及完整的mode类#… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
GitHub - September26/java-algorithms: 算法题汇总包含牛客leetCodelintCode等网站题目的解法和代码以及完整的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 106n queries.length1 n 1051 queries[i] 106 解题思路
这道题其实可以分成寻找小于等于target的数中最大的以及大于等于target的数中最小的。
寻找小于等于target的数中最大的数值属于典型的二叉树搜索构建一个方法searchValue进行二叉树递归遍历。
传入参数1:TreeNode root代表当前遍历的节点
传入参数2:int lastValue代表上一次匹配到的最合适的值
传入参数3:int target代表目标值。
方法中如果节点值等于目标值则直接返回当前值即可。
如果节点值大于目标值则递归搜索其左子树因为只有左子树的值才会比目标值小最合适的值仍然为上一次的因为这一次的不满足。
如果节点值小于目标值则递归搜索其左子树因为只有右子树的值才会比目标值大最合适的值调整为当前值因为本地的值符合匹配。
寻找大于等于target的数中最小的方法也是一样。
代码
方法1:
class Solution2476
{
public:vectorvectorint closestNodes(TreeNode *root, vectorint queries){vectorvectorint list;for (int i : queries){int i1 searchValue(root, true, -1, i);int i2 searchValue(root, false, -1, i);vectorint 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:vectorvectorint closestNodes(TreeNode *root, vectorint queries){vectorint sortList;vectorTreeNode * list;search(root, sortList);vectorvectorint 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, vectorint sortList){if (node nullptr)return;search(node-left, sortList);sortList.push_back(node-val);search(node-right, sortList);}
};
