作者:葬心xz | 来源:互联网 | 2023-09-18 16:32
GivenaBinarySearchTreeandatargetnumber,returntrueifthereexisttwoelementsintheBSTsuchthatth
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
题意:给定二进制搜索树和目标数字,如果BST中存在两个元素,使得它们的和等于给定目标,则返回true。
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
def findTarget(self, root, k):
"""
:type root: TreeNode
:type k: int
:rtype: bool
"""
if (not root):
return False
s = set()
queue = [root]
while (queue):
node = queue.pop(0)
s.add(node.val)
if(node.left):
queue.append(node.left)
if(node.right):
queue.append(node.right)
for num in s:
if k - num in s and 2 * (k - num) != k:
return True
return False
来自为知笔记(Wiz)
653. Two Sum IV - Input is a BST 两个数的和,输入为平衡二叉树