[leetcode] 653. Two Sum IV - Input is a BST

[leetcode] 653. Two Sum IV - Input is a BST

Description

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input:

5 / \ 3 6 / \ \2 4 7Target = 9

Output:

True

Example 2:

Input:

5 / \ 3 6 / \ \2 4 7Target = 28

Output:

False

分析

题目的意思是：给定一颗二叉树，判断是否存在两个数的和为target。

用一个set集合s把来存储每个节点的值，如果再遇见一个target-当前值存在这个集合里面，说明存在两个数，就直接返回正确了。

代码

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */class Solution {public: bool findTarget(TreeNode* root, int k) { if(!root) return false; unordered_set s; return solve(root,k,s); } bool solve(TreeNode* root, int k,unordered_set &s){ if(!root){ return false; } if(s.count(k-root->val)){ return true; } s.insert(root->val); return solve(root->left,k,s)||solve(root->right,k,s); }};

参考文献

​​[LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。