102.二叉树的层序遍历

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

示例：
二叉树：[3,9,20,null,null,15,7],

3
   / \
  9  20
    /  \
   15   7

返回其层序遍历结果：

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

解法一：BFS 迭代

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    if root == nil {
        return res
    }
    queue := []*TreeNode{root}
    for len(queue) > 0 {
        size := len(queue)
        temp := []int{}
        for i := 0; i < size; i++ {
            var top *TreeNode
            top, queue = queue[0], queue[1:]
            temp = append(temp, top.Val)
            if top.Left != nil {
                queue = append(queue, top.Left)
            }
            if top.Right != nil {
                queue = append(queue, top.Right)
            }
        }
        res = append(res, temp)
    }
    return res
}

解法二：DFS 递归

func levelOrder(root *TreeNode) [][]int {
    res := [][]int{}
    var dfs func(root *TreeNode, depth int)
    dfs = func(root *TreeNode, depth int) {
        if root == nil {
            return
        }
        if depth == len(res) {
            res = append(res, []int{})
        }
        res[depth] = append(res[depth], root.Val)
        dfs(root.Left, depth+1)
        dfs(root.Right, depth+1)
    }
    dfs(root, 0)
    return res
}