Given the root of a Binary Search Tree and a target number k, return true if there exist two elements in the BST such that their sum is equal to the given target.
Example 1:
Input: root = [5,3,6,2,4,null,7], k = 9
Output: true
Example 2:
Input: root = [5,3,6,2,4,null,7], k = 28
Output: false
Constraints:
The number of nodes in the tree is in the range [1, 10^4].
-10^4 <= Node.val <= 10^4
root is guaranteed to be a valid binary search tree.
-10^5 <= k <= 10^5
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
from collections import deque
class Solution:
def findTarget(self, root: Optional[TreeNode], k: int) -> bool:
q = deque()
q.append([root,k])
while q:
node, k = q.popleft()
now = node.val
if k-now != now:
now = k-now
answer = self.find_tree(root,now)
if answer == True:
return answer
if node.left !=None:
q.append([node.left,k])
if node.right !=None:
q.append([node.right, k])
return False
def find_tree(self,root,val):
#print(root.val, val)
tmp = False
if root.val == val:
return True
if root.left == None and root.right == None:
return False
if root.val>val and root.left !=None:
tmp = self.find_tree(root.left,val)
elif root.val <val and root.right != None:
tmp = self.find_tree(root.right,val)
return tmp
mapp = set()
mapp.add(k-n.val)