653. Two Sum IV - Input is a BST

653. Two Sum IV - Input is a BST

Question

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

Solution

• Method 1: recursion + HashMap O(NlogN) ```Java /**
  • Definition for a binary tree node.
  • public class TreeNode {
  • int val;
  • TreeNode left;
  • TreeNode right;
  • TreeNode(int x) { val = x; }
  • } */ class Solution { private Set set; public boolean findTarget(TreeNode root, int k) { if(root == null) return false; this.set = new HashSet<>(); return dfs(root, k); } private boolean dfs(TreeNode node, int k){ if(set.contains(k - node.val)) return true; else{ set.add(node.val); return (node.left != null ? dfs(node.left, k): false) || (node.right != null ? dfs(node.right, k): false); } } } ```