Python - simple BFS


  • 0
    S
    # Definition for a binary tree node.
    # class TreeNode(object):
    #     def __init__(self, x):
    #         self.val = x
    #         self.left = None
    #         self.right = None
    
    class Solution(object):
        def averageOfLevels(self, root):
            """
            :type root: TreeNode
            :rtype: List[float]
            """
            def bfs(root,result):
                if root:
                    q = []
                    q.append(root)
                    q.append(None)
                    xsum = 0
                    n    = 0
                    while q:
                        x = q.pop(0)
                        if x is None:
                            # new level found!
                            result.append( xsum / float(n ) )
                            xsum = 0
                            n    = 0
                            if q:
                                q.append(None)
                        else:
                            xsum += x.val
                            n    += 1
                            if x.left:
                                q.append(x.left)
                            if x.right:
                                q.append(x.right)
                    return result
            return bfs(root,[])

Log in to reply
 

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