LeetCode 二叉搜索树中两个节点之和

剑指 Offer II 056. 二叉搜索树中两个节点之和

给定一个二叉搜索树的 根节点 root 和一个整数 k , 请判断该二叉搜索树中是否存在两个节点它们的值之和等于 k 。假设二叉搜索树中节点的值均唯一。

输入: root = [8,6,10,5,7,9,11], k = 12 输出: true 解释: 节点 5 和节点 7 之和等于 12

来源：LeetCode

其实就是一边遍历并且要一边判断是否有和相加等于k。 用哈希表来存储遍历过的节点，每遍历一个节点就在哈希表寻找有没有符合条件的； 其实相当于每遍历一个节点，都会与其之前的节点相加进行判断，有符合条件的，返回true，没有就将节点加入哈希表； 之后就是节点的移动，左右子节点只要有一个满足条件就可以返回true。

class Solution {
    Set set = new HashSet();

    public boolean findTarget(TreeNode root, int k) {
        if(root==null)
            return false;
        if(set.contains(k-root.val)){
            return true;
        }
        set.add(root.val);
        return findTarget(root.left,k) || findTarget(root.right,k);
    }
}

参考：官方题解方法一