问题描述

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

示例：
二叉树：[3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：

[
  [3],
  [9,20],
  [15,7]
]

解题思路

二叉树的层序遍历比较基础，想法很简单，就是用一个queue就可以实现，一次把弹出节点的左右子节点放入queue中，然后读出就行。

然而这个题，要求同一层结点数据放在一个[]中，这个地方就是我们要思考的地方！

在队列中添加子节点的同时，要把同一层的结点放在一起操作，这里就需要获得这一层结点的数量，然后在这个数量中再循环看看是否还有子节点，然后继续放入队列中。

代码实现

from queue import Queue

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None

class Solution:
    def levelOrder(self, root: TreeNode) -> List[List[int]]:
        results = [] #放最终结果
        que = Queue() #暂存队列
        if root:
            results.append([root.val])
            que.put(root)
        while not que.empty():
            quelength = que.qsize() #获取同层结点的数量，因为同层的结点同时在队列里
            cell = [] #存放每层的结点val
            for i in range(quelength):
                node = que.get()
                if node.left:
                    cell.append(node.left.val)
                    que.put(node.left)
                if node.right:
                    cell.append(node.right.val)
                    que.put(node.right)
                quelength -= 1
            if cell :
                results.append(cell)
        return results

问题变种

如何求每层的平均值？

给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

示例 1：

输入：
    3
   / \
  9  20
    /  \
   15   7
输出：[3, 14.5, 11]
解释：
第 0 层的平均值是 3 ,  第1层是 14.5 , 第2层是 11 。因此返回 [3, 14.5, 11] 。

提示：

• 节点值的范围在32位有符号整数范围内。

代码实现：

class Solution:
    def averageOfLevels(self, root: TreeNode) -> List[float]:
        results = []
        que = Queue()
        if root:
            results.append(root.val)
            que.put(root)
        while not que.empty():
            quelength = que.qsize()
            sum = 0
            count = 0
            for i in range(quelength):
                node = que.get()
                if node.left:
                    sum += node.left.val
                    que.put(node.left)
                    count += 1
                if node.right:
                    sum += node.right.val
                    que.put(node.right)
                    count += 1
            if count!=0:
                avg = sum / count
                results.append(avg)
        return results