剑指 Offer II 056. 二叉搜索树中两个节点之和
2023-09-27 14:26:25 时间
给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。
示例 1:
输入: root = [8,6,10,5,7,9,11], k = 12
输出: true
解释: 节点 5 和节点 7 之和等于 12
示例 2:
输入: root = [8,6,10,5,7,9,11], k = 22
输出: false
解释: 不存在两个节点值之和为 22 的节点
提示:
二叉树的节点个数的范围是 [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<int> ans;
void bfs(TreeNode *root) {
if (!root) return;
bfs(root->left);
ans.push_back(root->val);
bfs(root->right);
}
bool findTarget(TreeNode* root, int k) {
bfs(root);
int l = 0, r = ans.size() - 1;
while (l < r) {
if (ans[l] + ans[r] > k) {
r--;
} else if (ans[l] + ans[r] < k) {
l++;
} else {
return true;
}
}
return false;
}
};
相关文章
- 【BZOJ2003】[HNOI2010]矩阵(搜索)
- 【洛谷4005】小Y和地铁(搜索)
- Laravel 多 where 并搜索
- 谷歌搜索技巧
- 47分布式电商项目 - 商品关键字搜索
- C#,字符串匹配(模式搜索)KMP算法的源代码与数据可视化
- 搜索旋转排序数组
- 如何用华为位置服务实现搜索位置返回父子节点信息
- 拯救狗盲症,搜狗图片搜索一步精准识狗
- 二叉搜索树(BST)——Treap树
- Nvidia GPU 入门教程之 09 如何使用 Kaggle API 搜索和下载数据?
- vue--去除input输入框--空格--适用于搜索查询框
- 力扣解法汇总450-删除二叉搜索树中的节点
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 《剑指offer》-- 序列化二叉树、二叉搜索树的第k个节点、数据流中的中位数、滑动窗口的最大值
- 109、【树与二叉树】leetcode ——701. 二叉搜索树中的插入操作:递归法+双指针迭代法(C++版本)
- FireDAC 下的 Sqlite [10] - 使用 R-Tree 搜索
- 剑指 Offer 54. 二叉搜索树的第k大节点
- 思博伦协助改进海上搜索与救援行动
- 微软关闭Docs.com搜索功能:个人隐私信息被公开
- 百度搜索框搜索时显示或者隐藏历史搜索记录