二叉树的层序遍历

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

最开始的代码

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    res := [][]int{{}} // 初始化

    level := 0                                    // 当前在哪一层
    countOfCurrentLevel, countOfNextLevel := 1, 0 // 当前层和接下来一层的剩余节点数

    stack := list.New() // bfs 的 stack
    stack.PushBack(root)

    for stack.Len() != 0 {
        if countOfCurrentLevel == 0 { // 如果当前层剩余节点数为0
            res = append(res, []int{})                                  // 扩容
            level += 1                                                  // 层数加一
            countOfCurrentLevel, countOfNextLevel = countOfNextLevel, 0 //接下来一层的节点数就变成了当前层的
        }
        p := stack.Remove(stack.Front()).(*TreeNode) // 先进先出
        countOfCurrentLevel -= 1                     // 弹出了一个
        res[level] = append(res[level], p.Val)       // 打印
        if p.Left != nil {
            stack.PushBack(p.Left) // 每一次放入 stack 中都要计数
            countOfNextLevel += 1
        }
        if p.Right != nil {
            stack.PushBack(p.Right)
            countOfNextLevel += 1
        }
    }
    return res
}

然后想到其实不需要俩计数器的

func levelOrder(root *TreeNode) [][]int {
    if root == nil {
        return [][]int{}
    }
    res := [][]int{} // 初始化

    level := -1 // 当前在哪一层

    stack := list.New() // bfs 的 stack
    stack.PushBack(root)

    for stack.Len() != 0 {
        res = append(res, []int{}) // 扩容
        level += 1                 // 层数加一
        stackLen := stack.Len()
        for i := 0; i < stackLen; i++ {
            p := stack.Remove(stack.Front()).(*TreeNode) // 先进先出
            res[level] = append(res[level], p.Val)       // 打印
            if p.Left != nil {
                stack.PushBack(p.Left) 
            }
            if p.Right != nil {
                stack.PushBack(p.Right)
            }
        }
    }
    return res
}

有一个值得注意的问题是for i := 0; i < stackLen; i++这里，不能写成for i := 0; i < stack.Len(); i++

因为循环里面会改变stack