69. 二叉树的层次遍历

69. 二叉树的层次遍历

中文English

给出一棵二叉树，返回其节点值的层次遍历（逐层从左往右访问）

样例

样例 1:

输入：{1,2,3}
输出：[[1],[2,3]]
解释：
   1
  / 
 2   3
它将被序列化为{1,2,3}
层次遍历

样例 2:

输入：{1,#,2,3}
输出：[[1],[2],[3]]
解释：
1
 
  2
 /
3
它将被序列化为{1,#,2,3}
层次遍历

挑战

挑战1：只使用一个队列去实现它

挑战2：用BFS算法来做

注意事项

• 首个数据为根节点，后面接着是其左儿子和右儿子节点值，"#"表示不存在该子节点。
• 节点数量不超过20。

输入测试数据 (每行一个参数)如何理解测试数据？

 BFS写法

"""
Definition of TreeNode:
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None
"""

class Solution:
    """
    @param root: A Tree
    @return: Level order a list of lists of integer
    """
    def levelOrder(self, root):
        # write your code here
        #层次遍历，每一层一个列表，队列的方式,每一层的节点丢进来
        if not root: return []
        
        #初始化
        results = []
        #初始节点
        queue = [root]
        
        while queue:
            #循环每一层丢进来的节点
            length = len(queue)
            temp_results = []
            for i in range(length):
                pop_num = queue.pop(0)
                temp_results.append(pop_num.val)
                if pop_num.left:
                    queue.append(pop_num.left)
                if pop_num.right:
                    queue.append(pop_num.right)
        
            results.append(temp_results)
        
        return results