# 653. Two Sum IV - Input is a BST 两数之和 IV - 输入 BST

@TOC

## # 题目描述

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
``````

## # 解题方法

### # 方法一：BFS

``````[5,3,6,2,4,null,7]
9
``````

``````5
[5, 3, 6]
3
[5, 3, 6, 2, 4]
6
``````
``````# 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
bfs, s = [root], set()
for i in bfs:
print i.val
if k - i.val in s : return True
if i.left : bfs.append(i.left)
if i.right : bfs.append(i.right)
print([b.val for b in bfs])
return False
``````

``````# 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
"""
que = collections.deque()
que.append(root)
res = set()
while que:
size = len(que)
for _ in range(size):
node = que.popleft()
if not node:
continue
if k - node.val in res:
return True
que.append(node.left)
que.append(node.right)
return False
``````

### # 方法二：DFS

``````# 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
"""
res = self.inOrder(root)
resset = set(res)
for num in res:
if k != 2 * num and k - num in resset:
return True
return False

def inOrder(self, root):
if not root:
return []
res = []
res.extend(self.inOrder(root.left))
res.append(root.val)
res.extend(self.inOrder(root.right))
return res
``````

DFS过程中进行判断：

``````# 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
"""
res = set()
def inOrder(root):
if not root:
return False
if k - root.val in res:
return True