closest-nodes-queries-in-a-binary-search-tree

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given the <code>root</code> of a binary search tree and an array <code>queries</code> of size <code>n</code> consisting of positive integers.

Find a 2D array <code>answer</code> of size <code>n</code> where <code>answer[i] = [mini, maxi]</code>:

<ul>
	<li><code>mini</code> is the largest value in the tree that is smaller than or equal to <code>queries[i]</code>. If a such value does not exist, add <code>-1</code> instead.</li>
	<li><code>maxi</code> is the smallest value in the tree that is greater than or equal to <code>queries[i]</code>. If a such value does not exist, add <code>-1</code> instead.</li>
</ul>

Return the array <code>answer</code>.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/28/bstreeedrawioo.png" style="width: 261px; height: 281px;" />
<pre>
Input: root = [6,2,13,1,4,9,15,null,null,null,null,null,null,14], queries = [2,5,16]
Output: [[2,2],[4,6],[15,-1]]
Explanation: We answer the queries in the following way:
- The largest number that is smaller or equal than 2 in the tree is 2, and the smallest number that is greater or equal than 2 is still 2. So the answer for the first query is [2,2].
- The largest number that is smaller or equal than 5 in the tree is 4, and the smallest number that is greater or equal than 5 is 6. So the answer for the second query is [4,6].
- The largest number that is smaller or equal than 16 in the tree is 15, and the smallest number that is greater or equal than 16 does not exist. So the answer for the third query is [15,-1].
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/09/28/bstttreee.png" style="width: 101px; height: 121px;" />
<pre>
Input: root = [4,null,9], queries = [3]
Output: [[-1,4]]
Explanation: The largest number that is smaller or equal to 3 in the tree does not exist, and the smallest number that is greater or equal to 3 is 4. So the answer for the query is [-1,4].
</pre>

&nbsp;
Constraints:

<ul>
	<li>The number of nodes in the tree is in the range <code>[2, 105]</code>.</li>
	<li><code>1 &lt;= Node.val &lt;= 106</code></li>
	<li><code>n == queries.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries[i] &lt;= 106</code></li>
</ul>

closestNodes

Closest Nodes Queries in a Binary Search Tree

Closest Binary Search Tree Value

closest-binary-search-tree-value

最接近的二叉搜索树值

Closest Binary Search Tree Value II

closest-binary-search-tree-value-ii

最接近的二叉搜索树值 II

Search in a Binary Search Tree

search-in-a-binary-search-tree

二叉搜索树中的搜索

Tree

Depth-First Search

Binary Search Tree

Array

Binary Search

Binary Tree

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

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

<ul>
	<li><code>mini</code> 是树中小于等于&nbsp;<code>queries[i]</code> 的 最大值 。如果不存在这样的值，则使用 <code>-1</code> 代替。</li>
	<li><code>maxi</code> 是树中大于等于&nbsp;<code>queries[i]</code> 的 最小值 。如果不存在这样的值，则使用 <code>-1</code> 代替。</li>
</ul>

返回数组 <code>answer</code> 。

&nbsp;

示例 1 ：

<img alt="" src="https://assets.leetcode.com/uploads/2022/09/28/bstreeedrawioo.png" style="width: 261px; height: 281px;" />

<pre>
输入：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] 。
</pre>

示例 2 ：

<img alt="" src="https://assets.leetcode.com/uploads/2022/09/28/bstttreee.png" style="width: 101px; height: 121px;" />

<pre>
输入：root = [4,null,9], queries = [3]
输出：[[-1,4]]
解释：树中不存在小于等于 3 的最大值，且大于等于 3 的最小值是 4 。所以查询的答案是 [-1,4] 。
</pre>

&nbsp;

提示：

<ul>
	<li>树中节点的数目在范围 <code>[2, 105]</code> 内</li>
	<li><code>1 &lt;= Node.val &lt;= 106</code></li>
	<li><code>n == queries.length</code></li>
	<li><code>1 &lt;= n &lt;= 105</code></li>
	<li><code>1 &lt;= queries[i] &lt;= 106</code></li>
</ul>