給定一棵二叉搜索樹，問是否存在兩個(gè)節(jié)點(diǎn)的數(shù)之和等于給定值k
DFS的同時(shí)記錄vis過的節(jié)點(diǎn)（因?yàn)锽ST性質(zhì)，節(jié)點(diǎn)的值各不相同），如果k-當(dāng)前節(jié)點(diǎn)的值處于已經(jīng)vis過的列表中，則return True，vis使用Python的set()
1 #653
2 #Runtime: 85 ms
3 #Memory Usage: 18.3 MB
4
5 # Definition for a binary tree node.
6 # class TreeNode(object):
7 # def __init__(self, val=0, left=None, right=None):
8 # self.val = val
9 # self.left = left
10 # self.right = right
11 class Solution(object):
12
13 def SearchBST(self, r, k, vis):
14 if not r:
15 return False
16 if k - r.val in vis:
17 return True
18 vis.add(r.val)
19 return self.SearchBST(r.left, k, vis) or self.SearchBST(r.right, k, vis)
20
21
22 def findTarget(self, root, k):
23 """
24 :type root: TreeNode
25 :type k: int
26 :rtype: bool
27 """
28 return self.SearchBST(root, k, set())