Python BFS recursive


  • 0
    M

    Collect children from every node in one level, put them in a list.
    Calculate the avg of every node value in one level, put them in a list.

    Pass these two lists to the next recursion. When no more node can be accessed, return the list with avg values.

    
    def averageOfLevels(self, root):
            """
            :type root: TreeNode
            :rtype: List[float]
            """
            return self.avgHelper([root],[])
            
            
            
        def avgHelper(self,children, avg):
            if len(children) == 0:
                return avg
            nextChildren = []
            avgVal = 0
            for i in children:
                avgVal += i.val
                if i.left:
                    nextChildren.append(i.left)
                if i.right:
                    nextChildren.append(i.right)
            avgVal = avgVal*1.0 / len(children)
            avg.append(avgVal)
            return self.avgHelper(nextChildren, avg)
    
    
    

Log in to reply
 

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