介绍

层序遍历，顾名思义，不难理解，就是一层一层地遍历

Golang实现

此处分为递归实现（DFS，深度优先算法）和迭代实现（BFS，广度优先算法）

本文以Leetcode102题为例：https://leetcode-cn.com/problems/binary-tree-level-order-traversal/

递归实现（DFS）

递归实现需要储存每层的级数

实现起来主要分为以下几个步骤

1. 递归跳出条件：本节点为空
2. 查看结果slice大小是否等于层数，若相等则进行扩容操作
3. 将本节点存入结果slice对应的层数
4. 对左节点进行遍历
5. 对右节点进行遍历

代码：

package leetcode

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

var ans [][]int

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

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

迭代实现（BFS，使用队列）

步骤如下：

1. 将根节点放入队列
2. 获取当前队列长度，此时当前队列内的所有节点代表该层的所有节点
3. 将该层的所有节点依次从队列中取出，将该节点值存入该层的结果slice中，并将该节点的子节点放入队列
4. 重复步骤2、3 直到队列为空

代码实现：

package leetcode

import "container/list"

// TreeNode Definition for a binary tree node.
type TreeNode struct {
    Val   int
    Left  *TreeNode
    Right *TreeNode
}

func levelOrder(root *TreeNode) [][]int {
    var ans [][]int
    if root == nil {
        return ans
    }
    queue := list.New()
    queue.PushFront(root)
    for queue.Len() > 0 {
        var arr []int
        length := queue.Len()
        for i := 0; i < length; i++ {
            node := queue.Remove(queue.Back()).(*TreeNode)
            arr = append(arr, node.Val)
            if node.Left != nil {
                queue.PushFront(node.Left)
            }
            if node.Right != nil {
                queue.PushFront(node.Right)
            }
        }
        ans = append(ans, arr)
    }

    return ans
}