## 题目描述：

LeetCode 653. 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
```

## Python代码：

``````# 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
"""
self.root = root
self.k = k
return self.findNumber(root)
def findNumber(self, root):
if not root: return False
node = self.root
n = self.k - root.val
if n != root.val:
while node:
if node.val == n: return True
if n > node.val: node = node.right
else: node = node.left
return self.findNumber(root.left) or self.findNumber(root.right)
``````

## Python代码：

``````# 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
"""
self.dset = set()
self.traverse(root)
for n in self.dset:
if k - n != n and k - n in self.dset:
return True
return False
def traverse(self, root):
if not root: return
self.traverse(root.left)
self.traverse(root.right)
``````

Pingbacks已关闭。

1. nobody 发布于 2018年3月9日 11:37 #

第一种解法是不是有问题啊
每次查找只以当前子树的根节点为数A，然后数B只在当前子树里查找
如果A和B在不同的子树里，A/B都不在另一个节点从根到该节点的路径上，就找不到了