Python BFS traverse tree and use hash to search


  • 0
    V
    class Solution(object):
        def findTarget(self, root, k):
            """
            :type root: TreeNode
            :type k: int
            :rtype: bool
            """
            
            nwq,nxq=[root],[]
            hashset=set([])
            #BFS
            while True:
                while nwq:
                    cur=nwq.pop()
                    if cur.left:nxq.append(cur.left)
                    if cur.right:nxq.append(cur.right)
                    y=k-cur.val
                    #hash search
                    if y in hashset:
                        return True
                    
                    hashset.add(cur.val)
                if nxq:
                    nwq=nxq
                    nxq=[]
                else:
                    break
            return False
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.