LeetCode 题解工作台
二叉搜索树最近节点查询
给你一个 二叉搜索树 的根节点 root ，和一个由正整数组成、长度为 n 的数组 queries 。 请你找出一个长度为 n 的 二维 答案数组 answer ，其中 answer[i] = [min i , max i ] ： min i 是树中小于等于 queries[i] 的 最大值 。如果…
6
题型
6
代码语言
3
相关题
当前训练重点
中等 · 二分·树·traversal
答案摘要
由于题目中给出的是一棵二叉搜索树，因此我们可以通过中序遍历得到一个有序数组，然后对于每个查询，我们可以通过二分查找得到小于等于该查询值的最大值和大于等于该查询值的最小值。 时间复杂度 $O(n + m \times \log n)$，空间复杂度 。其中 和 分别是二叉搜索树中的节点数和查询数。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 二分·树·traversal 题型思路
题目描述
给你一个 二叉搜索树 的根节点 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
解题思路
方法一：中序遍历 + 二分查找
由于题目中给出的是一棵二叉搜索树，因此我们可以通过中序遍历得到一个有序数组，然后对于每个查询，我们可以通过二分查找得到小于等于该查询值的最大值和大于等于该查询值的最小值。
时间复杂度 ，空间复杂度 。其中 和 分别是二叉搜索树中的节点数和查询数。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def closestNodes(
self, root: Optional[TreeNode], queries: List[int]
) -> List[List[int]]:
def dfs(root: Optional[TreeNode]):
if root is None:
return
dfs(root.left)
nums.append(root.val)
dfs(root.right)
nums = []
dfs(root)
ans = []
for x in queries:
i = bisect_left(nums, x + 1) - 1
j = bisect_left(nums, x)
mi = nums[i] if 0 <= i < len(nums) else -1
mx = nums[j] if 0 <= j < len(nums) else -1
ans.append([mi, mx])
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
The candidate efficiently handles large inputs by reducing the problem to binary search on a sorted array.
- question_mark
Look for correct handling of edge cases, especially the absence of a larger or smaller value for a query.
- question_mark
The candidate demonstrates a solid understanding of binary search tree traversal and its application to solve problems efficiently.
常见陷阱
外企场景- error
Failing to optimize the solution for large inputs, resulting in a slower approach for processing the tree or queries.
- error
Incorrectly handling edge cases like when no smaller or larger node value exists for a query.
- error
Not converting the tree into a sorted array, leading to inefficient queries and unnecessary repeated traversal of the tree.
进阶变体
外企场景- arrow_right_alt
What if the queries are given in random order, should the approach be adjusted to handle this?
- arrow_right_alt
Consider a version where the tree is dynamic and can be updated between queries. How would that affect the solution?
- arrow_right_alt
What if you have multiple trees and need to process queries for each one separately?