我的个人微信公众号：Microstrong

微信公众号ID：MicrostrongAI

微信公众号介绍：Microstrong(小强)同学主要研究机器学习、深度学习、计算机视觉、智能对话系统相关内容，分享在学习过程中的读书笔记！期待您的关注，欢迎一起学习交流进步！

知乎主页：https://www.zhihu.com/people/MicrostrongAI/activities

Github：https://github.com/Microstrong0305

个人博客：https://blog.csdn.net/program_developer

102. Binary Tree Level Order Traversal

Given a binary tree, return the level order traversal of its nodes' values. (ie, from left to right, level by level).

For example:
Given binary tree [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

return its level order traversal as:

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

解题思路：

'''
思路：用队列实现

           1、root为空，则返回空表

           2、队列不为空，记下此时队列中的结点个数length，length个结点出队列的同时，记录结点值，并把结点的左右子结点加入队列
'''

from typing import List


# Definition for a binary tree node.
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]]:
        # write your code here
        res = []
        # 如果根结点为空，则返回空列表
        if root is None:
            return res
        # 模拟一个队列存储节点
        queue = []
        # 首先将根节点入队
        queue.append(root)
        # 列表为空时，循环终止
        while len(queue) != 0:
            # 使用列表存储同层节点
            levelValue = []
            # 记录同层节点的个数
            length = len(queue)
            for i in range(length):
                # 将同层节点依次出队
                temp = queue.pop(0)
                # 非空左孩子入队
                if temp.left is not None:
                    queue.append(temp.left)
                # 非空右孩子入队
                if temp.right is not None:
                    queue.append(temp.right)

                levelValue.append(temp.val)

            res.append(levelValue)
        return res


if __name__ == "__main__":
    root = TreeNode(3)
    level1_left = TreeNode(9)
    level1_right = TreeNode(20)
    root.left = level1_left
    root.right = level1_right

    level2_left = TreeNode(15)
    level2_right = TreeNode(7)
    level1_right.left = level2_left
    level1_right.right = level2_right

    sol = Solution()
    print(sol.levelOrder(root))

'''
Reference：
【1】https://blog.csdn.net/weixin_40314737/article/details/80942856
【2】https://blog.csdn.net/yurenguowang/article/details/76906620
'''