[LeetCode] Challenge log 637

Posted on | Edited on |
637. Average of Levels in Binary Tree

s1. Depth first traverse, record every node’s (value, level)

s2. Width first traverse, keep two queues as parent level and kid level.

Given a non-empty binary tree, return the average value of the nodes on each level in the form of an array.

Example 1:

1
2
3
4
5
6
7
8
9
Input:
    3
   / \
  9  20
    /  \
   15   7
Output: [3, 14.5, 11]
Explanation:
The average value of nodes on level 0 is 3,  on level 1 is 14.5, and on level 2 is 11. Hence return [3, 14.5, 11].

Note:

  1. The range of node’s value is in the range of 32-bit signed integer.
Soulution:
  1. DFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        if root is None: return []
        res = {}
        self.dst(root, 0, res)
        return [res[i][0]/res[i][1] for i in range(len(res))]
        
    def dst(self, root, level, res):
        if root.left is not None:
            self.dst(root.left, level + 1, res)
        if root.right is not None:
            self.dst(root.right, level + 1, res)
        if level not in res: 
            res[level] = [root.val, 1]
        else:
            res[level][0] += root.val
            res[level][1] += 1
  1. WFS
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def averageOfLevels(self, root):
        """
        :type root: TreeNode
        :rtype: List[float]
        """
        if root is None: return []
        parents = [root]
        kids = []
        tmp = 0
        count = 0
        res = []
        while len(parents) != 0 or len(kids) != 0:
            parent = parents.pop(0)
            tmp += parent.val
            count += 1
            if parent.left is not None: kids.append(parent.left)
            if parent.right is not None: kids.append(parent.right)
            if len(parents) == 0 :
                res.append(tmp/count)
                tmp = count = 0
                parents = kids
                kids = []
        return res
0%