Python, Straightforward with Explanation


  • 12

    Let's visit every node of the tree once, keeping track of what depth we are on. We can do this with a simple DFS.

    When we visit a node, info[depth] will be a two element list, keeping track of the sum of the nodes we have seen at this depth, and the number of nodes we have seen. This is necessary and sufficient to be able to compute the average value at this depth.

    At the end of our traversal, we can simply read off the answer.

    def averageOfLevels(self, root):
        info = []
        def dfs(node, depth = 0):
            if node:
                if len(info) <= depth:
                    info.append([0, 0])
                info[depth][0] += node.val
                info[depth][1] += 1
                dfs(node.left, depth + 1)
                dfs(node.right, depth + 1)
        dfs(root)
    
        return [s/float(c) for s, c in info]
    

  • 0
    L

    @awice hello! I cannot understand info[depth][0] += node.val and parameter root of dfs(root) . thank you


  • 0
    C

    @lusaty Not sure if you figured it out since your original post.

    Each element of info contains a list with the sum of all node values and a count of all nodes for each level of the tree. info[depth][0] += node.val adds the current node's value to the sum of node values for the depth level of the tree.

    The dfs() function performs a depth-first search of the tree, storing the sum and count of nodes for each level of the tree. dfs(root) starts this process with the given root node.


  • 0
    S

    Hi @lusaty . Think you would be able to understand the code below:

    1. Having a dictionary with key as the level and value as the sum of all nodes in that level
    2. Result is a list that contains the average of number of nodes in that level
    class Solution(object):
        def averageOfLevels(self, root):
            """
            :type root: TreeNode
            :rtype: List[float]
            """
            def helper(root, level):
                if not root:
                    return
                self.ans[level] += [root.val]
                helper(root.left, level+1)
                helper(root.right, level+1)
            
            if not root:
                return []
            self.ans = collections.defaultdict(list)
            result = []
            helper(root, 1)
            for key, value in self.ans.items():
                result.append(float(sum(value))/len(value))
            return result
    

  • 0
    L

    Really Straightforward!!!


Log in to reply
 

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