分享程序员开发的那些事...
更新时间：2022-09-02 21:09:32
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
这道题又是一道2sum的变种题，博主一直强调，平生不识TwoSum，刷尽LeetCode也枉然！只要是两数之和的题，一定要记得用哈希表来做，这道题只不过是把数组变成了一棵二叉树而已，换汤不换药，我们遍历二叉树就行，然后用一个哈希set，在递归函数函数中，如果node为空，返回false。如果k减去当前结点值在哈希set中存在，直接返回true；否则就将当前结点值加入哈希set，然后对左右子结点分别调用递归函数并且或起来返回即可，参见代码如下：
解法一：
public: bool findTarget(TreeNode* root, int k) { if (!root) return false; unordered_set<int> s; return helper(root, k, s); } bool helper(TreeNode* node, int k, unordered_set<int>& s) { if (!node) return false; if (s.count(k - node->val)) return true; s.insert(node->val); return helper(node->left, k, s) || helper(node->right, k, s); } };
我们也可以用层序遍历来做，这样就是迭代的写法了，但是利用哈希表的精髓还是没变的，参见代码如下：
解法二：
public: bool findTarget(TreeNode* root, int k) { if (!root) return false; unordered_set<int> s; queue<TreeNode*> q{{root}}; while (!q.empty()) { auto t = q.front(); q.pop(); if (s.count(k - t->val)) return true; s.insert(t->val); if (t->left) q.push(t->left); if (t->right) q.push(t->right); } return false; } };
参考资料：
https://discuss.leetcode.com/topic/98440/java-c-three-simple-methods-choose-one-you-like
https://discuss.leetcode.com/topic/100110/my-c-non-recursive-solution-using-unordered_set-and-stack
本文转自博客园Grandyang的博客，原文链接：[LeetCode] Two Sum IV - Input is a BST 两数之和之四 - 输入是二叉搜索树
，如需转载请自行联系原博主。