给定一棵二叉搜索树,问是否存在两个节点的数之和等于给定值k
DFS的同时记录vis过的节点(因为BST性质,节点的值各不相同),如果k-当前节点的值处于已经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())