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

题目来源

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

题目概述

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

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

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

思路分析

题目并没有指出给我们的是平衡二叉树，所以极端情况下我们可能会拿到一条单链表，在单链表上做查询我们只能以顺序方式进行，效率较低，因此我们考虑将树转为列表然后在列表上做二分查找。

代码实现

java实现

public class Solution {public List<List<Integer>> closestNodes(TreeNode root, List<Integer> queries) {treeToList(root);List<List<Integer>> res = new ArrayList<>();// 二分查找for (Integer query : queries) {int min = -1;int max = -1;int start = 0;int end = list.size();int mid =  0;while (start < end) {mid = start + (end - start) / 2;if (list.get(mid) >= query) {end = mid;} else if (list.get(mid) < query) {start = mid + 1;}}if (start < list.size()) {max = list.get(start);if (query.equals(max)) {min = query;}}if (min == -1 && start > 0) {min = list.get(start - 1);}List<Integer> temp = new ArrayList<>();temp.add(min);temp.add(max);res.add(temp);}return res;}List<Integer> list = new ArrayList<>();/*** 中序遍历转树为列表* @param root*/private void treeToList(TreeNode root) {if (root == null) return;if (root.left != null) treeToList(root.left);list.add(root.val);if (root.right != null) treeToList(root.right);}
}

c++实现

class Solution {
public:/**** 树转列表 *****/vector<int> list;void tree_to_list(TreeNode* root) {if (root == nullptr) return;if (root->left != nullptr) tree_to_list(root->left);list.push_back(root->val);if (root->right != nullptr) tree_to_list(root->right);}vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) {tree_to_list(root);vector<vector<int>> res;// 二分查找for (int query : queries) {int min = -1;int max = -1;int start = 0;int end = list.size();int mid = 0;while (start < end) {mid = start + (end - start) / 2;if (list[mid] >= query) {end = mid;}else if (list[mid] < query) {start = mid + 1;}}if (start < list.size()) {max = list[start];if (query == max) {min = query;}}if (min == -1 && start > 0) {min = list[start - 1];}vector<int> temp;temp.push_back(min);temp.push_back(max);res.push_back(temp);}return res;}
}