Uriel's Corner

Research Associate @ Harvard University / Research Interests: Computer Vision, Biomedical Image Analysis, Machine Learning
posts - 0, comments - 50, trackbacks - 0, articles - 594
给定一棵二叉搜索树,问是否存在两个节点的数之和等于给定值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())



只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理