专业的单位网站开发,网站如何做提现功能,书画协会网站建设,三水网站建设公司【LetMeFly】2476.二叉搜索树最近节点查询#xff1a;中序遍历 二分查找
力扣题目链接#xff1a;https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/
给你一个 二叉搜索树 的根节点 root #xff0c;和一个由正整数组成、长度为 n 的数组 qu…【LetMeFly】2476.二叉搜索树最近节点查询中序遍历 二分查找
力扣题目链接https://leetcode.cn/problems/closest-nodes-queries-in-a-binary-search-tree/
给你一个 二叉搜索树 的根节点 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
方法一中序遍历 二分查找
首先要明确的是 题目给的二叉搜索树不一定是平衡树。因此最坏的情况下题目给的二叉搜索树可能会退化成一条链单词搜索的时间复杂度可能会达到 O ( n ) O(n) O(n)。 因为可能有很多次查询 1 0 5 10^5 105所以我们可以预处理二叉搜索树 我们知道二叉搜索树的中序遍历结果是递增的因此我们中序遍历一遍二叉搜索树就得到了二叉树所有节点值的递增数组。 这样我们只需要遍历每一个查询二分查找想要的答案即可 对于查询 q q q使用内置函数lower_bound/bisect_left等找到第一个 ≥ q \geq q ≥q的位置 l o c loc loc。 判断 l o c loc loc是否超出数组范围 若超出说明无比 q q q大的数 M M M应为默认值-1否则 M v [ l o c ] Mv[loc] Mv[loc]。此时若 M M M恰好等于 q q q则可直接得到 m M mM mM m m m仍未默认值-1的话还要判断 l o c loc loc是否非零 若非零则 m v [ l o c − 1 ] mv[loc-1] mv[loc−1]否则 m m m为默认值-1 时间复杂度 O ( N Q log N ) O(NQ\log N) O(NQlogN)其中 N N N是二叉树节点个数 Q Q Q是查询个数空间复杂度 O ( N ) O(N) O(N)
AC代码
C
class Solution {
private:vectorint v;void dfs(TreeNode* root) {if (!root) {return;}dfs(root-left);v.push_back(root-val);dfs(root-right);}public:vectorvectorint closestNodes(TreeNode* root, vectorint queries) {dfs(root);vectorvectorint ans(queries.size());for (int i 0; i queries.size(); i) {int m -1, M -1;vectorint::iterator it lower_bound(v.begin(), v.end(), queries[i]);if (it ! v.end()) {M *it;if (M queries[i]) {m M;goto loop;}}if (it ! v.begin()) {m *(it - 1);}loop:ans[i] {m, M};}return ans;}
};Python
# from typing import List, Optional
# from bisect import bisect_left# # Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val0, leftNone, rightNone):
# self.val val
# self.left left
# self.right rightclass Solution:def dfs(self, root: Optional[TreeNode]) - None:if not root:returnself.dfs(root.left)self.v.append(root.val)self.dfs(root.right)def closestNodes(self, root: TreeNode, queries: List[int]) - List[List[int]]:self.v []self.dfs(root)ans []for q in queries:m, M -1, -1loc bisect_left(self.v, q)if loc ! len(self.v):M self.v[loc] # v1中这里笔误写成Mloc了if M q:ans.append([q, q])continueif loc:m self.v[loc - 1]ans.append([m, M])return ans同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/136269516
