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

Analysis

https://leetcode.com/articles/two-sum-iv/

BFS + HashSet

广度优先搜索，level order traversal：每一个节点遍历时，在hashset里面找是否存在target - currentNode.val，每一层的左右子节点依次放入queue，同时在hashset里面存入当前遍历的节点：

1. Remove an element,pp, from the front of thequeuequeue.

2. Check if the elementk-pk−palready exists in thesetset. If so, return True.

3. Otherwise, add this element,ppto thesetset. Further, add the right and the left child nodes of the current node to the back of thequeuequeue.

4. Continue steps 1. to 3. till thequeuequeuebecomes empty.

5. Return false if thequeuequeuebecomes empty.

BST In-order Traversal + Two Pointers

先in-order遍历BST，输出到一个list，再对这个list用2 sum的方法找target即可，因为list排序过，因此用two pointers很方便。

Solution

BFS + HashSet - Time: O(n), Space O(n)

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Queue<TreeNode> queue = new LinkedList();
        Set<Integer> set = new HashSet();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
            if (set.contains(k - node.val)) {
                return true;
            }
            set.add(node.val);
        }
        return false;
    }
}

BST inorder + Two Pointers

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        List < Integer > list = new ArrayList();
        inorder(root, list);
        int l = 0, r = list.size() - 1;
        while (l < r) {
            int sum = list.get(l) + list.get(r);
            if (sum == k)
                return true;
            if (sum < k)
                l++;
            else
                r--;
        }
        return false;
    }
    public void inorder(TreeNode root, List < Integer > list) {
        if (root == null)
            return;
        inorder(root.left, list);
        list.add(root.val);
        inorder(root.right, list);
    }
}

Recursive + HashSet

public class Solution {
    public boolean findTarget(TreeNode root, int k) {
        Set < Integer > set = new HashSet();
        return find(root, k, set);
    }
    public boolean find(TreeNode root, int k, Set < 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);
    }
}