漫画：二叉树系列 第二讲（层次遍历与BFS）

func levelOrder(root *TreeNode) [][]int {
    return dfs(root, 0, [][]int{})
}

func dfs(root *TreeNode, level int, res [][]int) [][]int {
    if root == nil {
        return res
    }
    if len(res) == level {
        res = append(res, []int{root.Val})
    } else {
        res[level] = append(res[level], root.Val)
    }
    res = dfs(root.Left, level+1, res)
    res = dfs(root.Right, level+1, res)
    return res
}

//go
func levelOrder(root *TreeNode) [][]int {
    var result [][]int
    if root == nil {
        return result
    }
    // 定义一个双向队列
    queue := list.New()
    // 插入根结点完成初始化
    queue.PushFront(root)
    // 进行广度搜索
    for queue.Len() > 0 {
        var current []int
        listLength := queue.Len()
        for i := 0; i < listLength; i++ {
            // 消耗尾部
            // queue.Remove(queue.Back()).(*TreeNode)：移除最后一个元素并将其转化为TreeNode类型
            node := queue.Remove(queue.Back()).(*TreeNode)
            current = append(current, node.Val)
            if node.Left != nil {
                //插入头部
                queue.PushFront(node.Left)
            }
            if node.Right != nil {
                queue.PushFront(node.Right)
            }
        }
        result = append(result, current)
    }
    return result
}