leetcode 653. 两数之和 IV - 输入 BST
给定一个二叉搜索树 root 和一个目标结果 k，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

示例 1：

输入: root = [5,3,6,2,4,null,7], k = 9
输出: true
示例 2：

输入: root = [5,3,6,2,4,null,7], k = 28
输出: false

提示:

二叉树的节点个数的范围是 [1, 104].
-104 <= Node.val <= 104
root 为二叉搜索树
-105 <= k <= 105

解答：Java
方法一：深度优先搜索 + 哈希表
思路和算法：
我们可以使用深度优先搜索的方式遍历整棵树，用哈希表记录遍历过的节点的值。
对于一个值为 xx 的节点，我们检查哈希表中是否存在 k - xk−x 即可。如果存在对应的元素，那么我们就可以在该树上找到两个节点的和为 kk；否则，我们将 xx 放入到哈希表中。
如果遍历完整棵树都不存在对应的元素，那么该树上不存在两个和为 kk 的节点。
方法二：广度优先搜索 + 哈希表
思路和算法：
我们可以使用广度优先搜索的方式遍历整棵树，用哈希表记录遍历过的节点的值。
具体地，我们首先创建一个哈希表和一个队列，将根节点加入队列中，然后执行以下步骤：
从队列中取出队头，假设其值为 xx；
检查哈希表中是否存在 k - xk−x，如果存在，返回 \text{True}True；
否则，将该节点的左右的非空子节点加入队尾；
重复以上步骤，直到队列为空；
如果队列为空，说明树上不存在两个和为 kk 的节点，返回 \text{False}False。

/**
 * 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<Integer> set = new HashSet<>();
    public boolean findTarget(TreeNode root, int k) {
        return helper(k,root);
    }
    public boolean helper(int k,TreeNode node){
        int target = k-node.val;
        if (set.contains(target)){
            return true;
        }
        set.add(node.val);
        boolean ans= false;
        if(node.left!=null){
            ans = helper(k,node.left);
        }
        if(node.right!=null&&!ans){
            ans= helper(k,node.right);
        }
        return ans;
    }
}

输入
[5,3,6,2,4,null,7]
9
[5,3,6,2,4,null,7]
28
输出
true
false
预期结果
true
false