LeetCode-【树】-653. 两数之和 IV - 输入 BST

给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

案例 1:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

输出: True
      

案例 2:

输入: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

输出: False      

题解：可能大多数人觉得本题很简单，嗯，我也这样想过，但真正做的时候，问题频出。

一般的思路：遍历树的每一个节点，用目标值减去这个节点值获得值x，然后再遍历一次二叉树，看是否能找到值等于x且不是当前节点的节点，如果找到，直接返回true，否则返回false；思路好像很清晰，好吧，想想代码实现，嗯。。，先是遍历二叉树，就用递归分别遍历左右子树好了，递归结束的条件，当然是找到符合要求的节点了，怎样判断节点符合要求，好像二叉树有个性质（每个节点的右子节点的值一定大于该节点的值，左子节点的值一定小于该节点的值），那遍历的时候就可通过值大小判断接下来应该遍历的节点是左还是右。好了，上代码。。。

class Solution {
    static boolean f;
    public static boolean dfs(TreeNode root,int x){
        if(root==null)
            return false;
        if(root.val==x){
            return true;
        }
        if(root.val<x){
            return dfs(root.right,x);
        }
        if(root.val>x){
            return dfs(root.left,x);
        }
        return false;
    }
    public static void find(TreeNode root,TreeNode cur,int k){
        if(cur==null){
            return;
        }
        if(f){
            return;
        }
        if(cur.val!=k-cur.val)
            f=dfs(root,k-cur.val);
        find(root,cur.left,k);
        find(root,cur.right,k);
        //return false;
    }
    public boolean findTarget(TreeNode root, int k) {
        if(root==null)
            return false;
        f=false;
        find(root,root,k);
        return f;
    }
}
           

使用set的层次遍历解法，层次遍历知道吧，set特性知道吧，不做过多解释了。。。

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        ArrayDeque<TreeNode> q=new ArrayDeque<>();
        Set<Integer> set=new HashSet<>();
        q.offer(root);
        while(!q.isEmpty()){
            root=q.poll();
            if(set.contains(k-root.val))
                return true;
            set.add(root.val);
            if(root.right!=null)
                q.offer(root.right);
            if(root.left!=null)
                q.offer(root.left);
        }
        return false;
    }
}