力扣2476.二叉搜索树最近节点查询
力扣2476.二叉搜索树最近节点查询
-
二叉搜索树 + 中序遍历 = 严格递增数组
- 在数组上做二分 找到第一个>=q的元素的下标j
- 若j < n 则a[j]为maxx
- 若j-1>0 && a[j] != p 则a[j-1]为minx
-
class Solution { vector<int> a; void dfs(TreeNode* node) { if(node == nullptr) return; dfs(node->left); a.push_back(node->val); dfs(node->right); } public: vector<vector<int>> closestNodes(TreeNode* root, vector<int>& queries) { dfs(root); int n = a.size(); vector<vector<int>> res; for(int q:queries) { //找第一个>=q元素的下标 int j = ranges::lower_bound(a,q) - a.begin(); int maxx = j < n ? a[j] : -1; //若j==n 说明当前q为最大值 j-1一定是<q的下标 if(j == n || a[j] != q) j --; int minx = j >= 0 ? a[j] : -1; res.push_back({minx,maxx}); } return res; } };
原文地址:https://blog.csdn.net/Pisasama/article/details/139782481
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!