python BFS


  • 3
    Y
        def averageOfLevels(self, root):
            """
            :type root: TreeNode
            :rtype: List[float]
            """
            res=[]
            if not root: return res
            q=[root]
            while q:
                q1=[]
                total=0
                cnt=0
                while q:
                    node =q.pop()
                    if node.left: q1.append(node.left)
                    if node.right: q1.append(node.right)
                    total+=node.val
                    cnt+=1
                res.append(total*1.0/cnt)
                q=list(q1)
            return res
    

  • 0
    L

    @yeyumujiang said in python BFS:

    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        res=[]
        if not root: return res
        q=[root]
        while q:
            q1=[]
            total=0
            cnt=0
            while q:
                node =q.pop()
                if node.left: q1.append(node.left)
                if node.right: q1.append(node.right)
                total+=node.val
                cnt+=1
            res.append(total*1.0/cnt)
            q=list(q1)
        return res
    

    I used BFS too. Curious why the time performance is so low.....Wonder whether there're faster ways to solve this problem. Btw, DFS isn't good either.


Log in to reply
 

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