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,104][1, 10^4][1,104].
• −104<=Node.val<=104-10^4 <= Node.val <= 10^4−104<=Node.val<=104
• 题目数据保证，输入的 root是一棵 有效 的二叉搜索树
• −105<=k<=105-10^5 <= k <= 10^5−105<=k<=105

解法：递归 + 哈希表

思路跟 两数之和 一样。

用一个 哈希表 uset记录已经遍历过的节点值。

如果 $k-root.val$ 存在哈希表 uset中，说明这棵树中存在两个数之和为 $k$ ，返回 true。其他情况都返回 false。

时间复杂度： $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);}
};