判断一棵树里是否有两个节点的值之和等于某个值。
653. Two Sum IV - Input is a BST
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 7
Target = 9
Output: True
Example 2:
Input:
5
/ 3 6
/ \ 2 4 7
Target = 28
Output: False
思路：使用 unordered_set存储??节点的值。
/** * 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 { private: unordered_set<int> s; bool dfs(TreeNode* root,int k, unordered_set<int>& s){ if(root==nullptr) return false; if(s.count(k-root->val)) return true; s.insert(root->val); return dfs(root->left,k,s)||dfs(root->right,k,s); } public: bool findTarget(TreeNode* root, int k) { s.clear(); return dfs(root,k,s); } };
python代码
创建集合 set(), 插入 add (c++ insert)
# Definition for a binary tree node. # class TreeNode(object): # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution(object): def helper(self,root,k,s): if not root: return False if k-root.val in s: return True s.add(root.val) return self.helper(root.left,k,s) or self.helper(root.right,k,s) def findTarget(self, root, k): """ :type root: TreeNode :type k: int :rtype: bool """ s=set() return self.helper(root,k,s)
原文：https://www.cnblogs.com/learning-c/p/9280596.html