Python beat 65% using queue, DFS and recursion


  • 0
    R

    Not the fastest solution possible, but this one got AC'ed. I keep a queue of the whole sum from the root to the current branch and I subtract from the highest item in the queue until there is no more items to subtract in the queue. This is not as efficient as the prefix sum solution and will probably get TLE if the branch is very very very deep.

    class Solution(object):
        def pathSum(self, root, sum):
            self.count = []
            self.summe = 0
            
            self.dfs(root, sum)
            return self.summe
            
        def checkCount(self, nodeVal, sum1):
            tmp = self.count
            sm = sum(tmp)
            if sm == sum1:
                self.summe += 1
            n = len(tmp)
            y = 0
            while n > 1:
                sm -= tmp[y]        
                if sm == sum1:
                    self.summe += 1
                y += 1
                n -= 1
    
        def dfs(self, node, sum):
            if node is None:
                return
            self.count.append(node.val)
            self.checkCount(node.val, sum)
            self.dfs(node.left,sum)
            self.dfs(node.right, sum)
            self.count.pop()
            return
    

Log in to reply
 

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