LeetCode 653. 两数之和 IV

思路

方法一：哈希表

遍历整棵树，找出所有可能的组合，判断是否存在和为 k 的一对节点。现在在此基础上做一些改进。

如果存在两个元素之和为 k，即 x+y=k，并且已知 x 是树上一个节点的值，则只需判断树上是否存在一个值为 y 的节点，使得 y=k-x。基于这种思想，在树的每个节点上遍历它的两棵子树（左子树和右子树），寻找另外一个匹配的数。在遍历过程中，将每个节点的值都放到一个哈希表中。对于每个值为 p 的节点，在哈希表中检查是否存在 k-p。如果存在，那么可以在该树上找到两个节点的和为 k；否则，将 p 放入到哈希表中。如果遍历完整棵树都没有找到一对节点和为 k，那么该树上不存在两个和为 k 的节点。

 1 class Solution {
 2 private:
 3     unordered_map<int, bool> mp;
 4 public:
 5     bool findTarget(TreeNode* root, int k) {
 6         if(root == NULL)    
 7             return false;
 8         if(mp.count(k - root->val) == 1)
 9             return true;
10         
11         mp[root->val] = true;
12         return findTarget(root->left, k) || findTarget(root->right, k);
13     }
14 };

方法二：利用BST的性质

BST的中序遍历序列是一个有序序列，先中序遍历得到此有序序列，这样就转化成了 LeetCode 167. 两数之和 II - 输入有序数组