二叉树的层序遍历golang

二叉树的层序遍历 - Golang实现

在计算机科学中，二叉树是一种常见的数据结构。层序遍历是一种广度优先搜索算法，用于遍历二叉树的每个节点。本文将使用Golang实现二叉树的层序遍历。

首先，我们需要定义二叉树的数据结构。

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

接下来，我们可以使用一个队列来实现层序遍历算法。我们将根节点入队并开始遍历。

func levelOrder(root *TreeNode) [][]int {
    result := [][]int{}
    if root == nil {
        return result
    }

    queue := []*TreeNode{root}
    for len(queue) > 0 {
        levelSize := len(queue)
        levelValues := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]
            levelValues = append(levelValues, node.Val)

            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }

        result = append(result, levelValues)
    }

    return result
}

这段代码中，我们首先定义了一个二维数组result，用于保存每层的节点值。然后，我们创建了一个队列queue，并将根节点入队。在主循环中，我们先获取当前层的节点数量levelSize，并声明一个空的slice levelValues，用于存储当前层的节点值。

在内部循环中，我们依次从队列中取出节点并将其值加入levelValues。如果该节点有左孩子或右孩子，我们将它们入队。完成一层的遍历后，将levelValues添加到result中。

最后，我们返回result，即二叉树的层序遍历结果。

让我们来测试一下我们的代码：

func main() {
    // 创建一个示例二叉树
    root := &TreeNode{
        Val: 3,
        Left: &TreeNode{Val: 9},
        Right: &TreeNode{
            Val: 20,
            Left: &TreeNode{Val: 15},
            Right: &TreeNode{Val: 7},
        },
    }

    result := levelOrder(root)
    fmt.Println(result) // [[3], [9, 20], [15, 7]]
}

在以上示例中，我们创建了一个二叉树并应用层序遍历算法。最终结果是一个包含三个层级的二维数组[[3], [9, 20], [15, 7]]。

总结来说，二叉树的层序遍历是一种常见的广度优先搜索算法。我们使用一个队列来实现此算法，遍历每个节点并将其子节点加入队列。通过不断迭代，我们可以逐层生成二叉树结构。

以上介绍了二叉树的层序遍历的Golang实现，希望能对大家理解二叉树和广度优先搜索算法有所帮助。