新闻资讯

质量为本、客户为根、勇于拼搏、务实创新

< 返回新闻资讯列表

golang二叉树层序遍历怎么实现,golang二叉树层序遍历

发布时间:2023-11-22 03:01:09

golang二叉树层序遍历怎样实现

要实现二叉树的层序遍历,可使用队列来辅助实现。

首先,我们需要定义二叉树的结构:

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

然后,我们可使用队列来辅助层序遍历:

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

    result := [][]int{}
    queue := []*TreeNode{root}

    for len(queue) > 0 {
        levelSize := len(queue)
        level := []int{}

        for i := 0; i < levelSize; i++ {
            node := queue[0]
            queue = queue[1:]

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

        result = append(result, level)
    }

    return result
}

该函数首先检查根节点是否是为空,如果为空则直接返回空的结果。

然后,我们创建一个队列,并将根节点放入队列中。

我们进入一个循环,直到队列为空。在每次循环中,我们记录当前队列的大小,这样我们就能够知道当前层级的节点数。

我们从队列中取出当前层级的节点,并将其值加入到该层级的结果数组中。然后,我们将该节点的左右子节点加入到队列中,以便下一层的遍历。

最后,我们将该层级的结果数组加入到终究结果数组中。

最后,返回终究结果数组就是二叉树的层序遍历结果。

请注意,以上代码仅提供了一种实现方式。在实际使用中,可能有区分的实现方式。