Leetcode653. 两数之和 IV - 输入二叉搜索树
题目链接
Leetcode653. 两数之和 IV - 输入二叉搜索树 easy
题目描述
给定一个二叉搜索树 root和一个目标结果 k，如果二叉搜索树中存在两个元素且它们的和等于给定的目标结果，则返回 true。
示例 1：
输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：
输入: root = [5,3,6,2,4,null,7], k = 28
输出: false
提示：
- 二叉树的节点个数的范围是 [ 1 , 1 0 4 ] [1, 10^4] [1,104].
- − 1 0 4 < = N o d e . v a l < = 1 0 4 -10^4 <= Node.val <= 10^4 −104<=Node.val<=104
- 题目数据保证，输入的
root是一棵 有效 的二叉搜索树 - − 1 0 5 < = k < = 1 0 5 -10^5 <= k <= 10^5 −105<=k<=105
解法：递归 + 哈希表
思路跟 两数之和 一样。
用一个 哈希表 uset记录已经遍历过的节点值。
如果
k
−
r
o
o
t
.
v
a
l
k - root.val
k−root.val 存在哈希表 uset中，说明这棵树中存在两个数之和为
k
k
k ，返回 true。其他情况都返回 false。
时间复杂度： O ( n ) O(n) O(n)
C++代码：
class Solution {
public:
unordered_set<int> uset;
bool findTarget(TreeNode* root, int k) {
if(root==nullptr) return false;
if(uset.count(k - root->val)) return true;
uset.insert(root->val);
return findTarget(root->left,k) || findTarget(root->right,k);
}
};