653. Two Sum IV - Input is a BST

653. Two Sum IV - Input is a BST

Given a Binary Search Tree and a target number, return true if there exist two elements in the BST such that their sum is equal to the given target.

Example 1:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 9

Output: True

Example 2:

Input: 
    5
   / \
  3   6
 / \   \
2   4   7

Target = 28

Output: False

My Solutions:

方法1：用一个hashset记录所有遇到的数字 root.val，想要找到k- root.val也在这个set里

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        HashSet<Integer> set = new HashSet<>();
        return find(root, k, set);
    }
    
    public boolean find(TreeNode root, int k, HashSet<Integer> set) {
        if (root == null) return false;
        if (set.contains(k - root.val)) return true;
        set.add(root.val);
        return find(root.left, k, set) || find(root.right, k, set);
    }
}

也可以用iterative的方法做：

class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set<Integer> seen = new HashSet<>();
        Queue<TreeNode> searchQueue = new LinkedList<>();
        
        if (root != null) searchQueue.add(root);
        
        while (!searchQueue.isEmpty()) {
            TreeNode current = searchQueue.remove();
            if (seen.contains(k - current.val)) return true;
            seen.add(current.val);
            if (current.left != null) searchQueue.add(current.left);
            if (current.right != null) searchQueue.add(current.right);
        }
        
        return false;
    }
}

方法2：根据bst的性质，可以进一步优化

class Solution {

    public boolean findTarget(TreeNode root, int k) {
        return dfs(root, root, k);
    }
    
    public boolean dfs(TreeNode root, TreeNode cur, int k) {
        // iterate on the cur node
        if(cur == null) return false;
        return search(root, cur, k - cur.val) 
            || dfs(root, cur.left, k) 
                || dfs(root, cur.right, k);
    }
    
    public boolean search(TreeNode root, TreeNode cur, int k){
        // search on the root node.
        
        if(root == null) return false;
        return (root.val == k) && (cur != root) //不能是同一个node加两遍
            || (root.val < k) && search(root.right, cur, k) //root的val已经比target小了，直接去右边找
                || (root.val > k) && search(root.left, cur, k); //直接去左边找
    }
}