一、题目描述

二、方法

基础题，二叉树版本的两数之和，dfs遍历这棵二叉搜索树，比如当前节点数值为val，那么就查哈希表key为k - val的键值对是否存在，如果存在则显然说明存在题目说的两个节点，如果不存在不能直接说明没这样的节点（因为可能这对节点才刚出现一个），而是存入该哈希表后继续遍历二叉树。实现中可以用集合set代替哈希表HashMap，速度会快一丢丢。

三、代码

java版本：

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    //哈希set
    Set<Integer> set = new HashSet<Integer>();
    
    public boolean findTarget(TreeNode root, int k) {
        if(root == null){
            return false;
        }
        if(set.contains(k - root.val)){
            return true;
        }
        //如果set中没有(k-root)元素，则把root值加入到哈希set中
        set.add(root.val);
        return findTarget(root.left, k) || findTarget(root.right, k);
    }
}

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
 

C++版本：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_set<int> hashtable;

    bool findTarget(TreeNode* root, int k) {
        if(root == nullptr){
            return false;
        }
        if(hashtable.count(k - root->val)){
            return true;
        }
        hashtable.insert(root->val);
        return findTarget(root->left, k) || findTarget(root->right, k);
    }
};

  

 

  
 
 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

文章来源: andyguo.blog.csdn.net，作者：山顶夕景，版权归原作者所有，如需转载，请联系作者。

原文链接：andyguo.blog.csdn.net/article/details/126908063