[102] 二叉树的层次遍历

难度：中等 题目来源：力扣（LeetCode） https://leetcode-cn.com/problems/binary-tree-level-order-traversal

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

示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其层次遍历结果：
[
[3],
[9,20],
[15,7]
]

解法：

type TreeNode struct {
    Left, Right *TreeNode
    Val         int
}
func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    ret := [][]int{}
    // 深度优先
    var dfsFunc func(root *TreeNode, level int)
    dfsFunc = func(root *TreeNode, level int) {
        if root == nil {
            return
        }
        if level == len(ret) {
            ret = append(ret, []int{root.Val})
        } else {
            ret[level] = append(ret[level], root.Val)
        }
        dfsFunc(root.Left, level+1)
        dfsFunc(root.Right, level+1)
    }
    dfsFunc(root, 0)
    // 广度优先
    // var bfsFunc func(root *TreeNode)
    // bfsFunc = func(root *TreeNode) {
    //     if root == nil {
    //         return
    //     }
    //     level, queue := 0, list.New()
    //     queue.PushBack(interface{}(root))
    //     for queue.Len() > 0 {
    //         length, element := queue.Len(), []int{}
    //         for i := 0; i < length; i++ {
    //             node := queue.Remove(queue.Front()).(*TreeNode)
    //             element = append(element, node.Val)
    //             if node.Left != nil {
    //                 queue.PushBack(interface{}(node.Left))
    //             }
    //             if node.Right != nil {
    //                 queue.PushBack(interface{}(node.Right))
    //             }
    //         }
    //         ret = append(ret, element)
    //         level++
    //     }
    // }
    // bfsFunc(root)
    return ret
}