题目描述

从上到下按层打印二叉树，同一层的结点按从左到右的顺序打印，每一层打印到一行。

样例

输入如下图所示二叉树[8, 12, 2, null, null, 6, null, 4, null, null, null]
    8
   / \
  12  2
     /
    6
   /
  4

输出：[[8], [12, 2], [6], [4]]

算法

(BFS) $O(n)$

宽度优先遍历，一层一层来做。即：

1. 将根节点插入队列中；
2. 创建一个新队列，用来按顺序保存下一层的所有子节点；
3. 对于当前队列中的所有节点，按顺序依次将儿子加入新队列，并将当前节点的值记录在答案中；
4. 重复步骤2-3，直到队列为空为止。

时间复杂度

树中每个节点仅会进队出队一次，所以时间复杂度是 $O(n)$。

参考文献

yxc大神的题解

Go 代码

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func get_Val(level[]*TreeNode)[]int{
    res:=[]int{}
    for _,v:=range level{
        res=append(res,v.Val)
    }
    return res
}
func printFromTopToBottom(root *TreeNode) [][]int {
    res:=[][]int{}
    if root==nil{
        return res
    }
    level:=[]*TreeNode{}
    level=append(level,root)
    res=append(res,get_Val(level))
    for true{
        newLevel:=[]*TreeNode{}
        for _,u:=range level{
            if u.Left!=nil{
                newLevel=append(newLevel,u.Left)
            }
            if u.Right!=nil{
                newLevel=append(newLevel,u.Right)
            }
        }
        if len(newLevel)!=0{
            res=append(res,get_Val(newLevel))
            level=newLevel
        }else{
            break
        }
    }
    return res
}