Go语言实现二叉树的层序遍历（小白也能学会的广度优先遍历教程）

图：一个简单的二叉树及其层序遍历结果 [1, 2, 3, 4, 5]

Go语言实现步骤

要实现层序遍历，我们需要借助一个队列（Queue）数据结构。Go 标准库没有内置队列，但我们可以用切片（slice）模拟队列行为。

1. 定义二叉树节点结构

type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}

2. 实现层序遍历函数

我们使用一个切片作为队列，初始时将根节点入队。然后循环处理队列中的节点：出队一个节点，将其值加入结果，再将其左右子节点（如果存在）依次入队。

func levelOrder(root *TreeNode) [][]int {    if root == nil {        return [][]int{}    }    var result [][]int    queue := []*TreeNode{root} // 初始化队列    for len(queue) > 0 {        levelSize := len(queue)        var currentLevel []int        // 处理当前层的所有节点        for i := 0; i < levelSize; i++ {            node := queue[0]            queue = queue[1:] // 出队            currentLevel = append(currentLevel, node.Val)            // 将子节点入队            if node.Left != nil {                queue = append(queue, node.Left)            }            if node.Right != nil {                queue = append(queue, node.Right)            }        }        result = append(result, currentLevel)    }    return result}

上面的代码返回的是一个二维切片，每一层对应一个子切片。如果你只需要一维的结果（即所有节点按顺序排列），可以稍作修改：

func levelOrderFlat(root *TreeNode) []int {    if root == nil {        return []int{}    }    var result []int    queue := []*TreeNode{root}    for len(queue) > 0 {        node := queue[0]        queue = queue[1:]        result = append(result, node.Val)        if node.Left != nil {            queue = append(queue, node.Left)        }        if node.Right != nil {            queue = append(queue, node.Right)        }    }    return result}

完整示例代码

package mainimport "fmt"type TreeNode struct {    Val   int    Left  *TreeNode    Right *TreeNode}func levelOrder(root *TreeNode) [][]int {    if root == nil {        return [][]int{}    }    var result [][]int    queue := []*TreeNode{root}    for len(queue) > 0 {        levelSize := len(queue)        var currentLevel []int        for i := 0; i < levelSize; i++ {            node := queue[0]            queue = queue[1:]            currentLevel = append(currentLevel, node.Val)            if node.Left != nil {                queue = append(queue, node.Left)            }            if node.Right != nil {                queue = append(queue, node.Right)            }        }        result = append(result, currentLevel)    }    return result}func main() {    // 构建示例树:    //       1    //      / \    //     2   3    //    / \    //   4   5    root := &TreeNode{Val: 1}    root.Left = &TreeNode{Val: 2}    root.Right = &TreeNode{Val: 3}    root.Left.Left = &TreeNode{Val: 4}    root.Left.Right = &TreeNode{Val: 5}    fmt.Println("层序遍历结果（分层）:", levelOrder(root))    // 输出: [[1] [2 3] [4 5]]}

总结

通过本教程，你已经掌握了如何在 Go语言 中实现 二叉树的层序遍历。这是学习 Go数据结构 的重要一步，也是面试中常见的算法题。

记住关键点：使用队列、逐层处理、先入先出（FIFO）。多练习几次，你就能熟练运用 广度优先遍历 解决各种树相关的问题了！

希望这篇教程对你有帮助！欢迎继续探索更多 Go 语言数据结构的奥秘。