二叉树的层序遍历（含十道leetcode相关题目）

文章目录

二叉树层序遍历模板
102. 二叉树的层序遍历

二叉树层序遍历模板

我们之前讲过了关于二叉树的深度优先遍历的文章：前中后序遍历的递归法和迭代法。

接下来我们再来介绍二叉树的另一种遍历方式：层序遍历。

层序遍历一个二叉树。就是从左到右一层一层的去遍历二叉树。这种遍历的方式和我们之前讲过的都不太一样。

需要借用一个辅助数据结构即队列来实现，队列先进先出，符合一层一层遍历的逻辑，而用栈先进后出适合模拟深度优先遍历也就是递归的逻辑。

而这种层序遍历方式就是图论中的广度优先遍历，只不过我们应用在二叉树上。

在这里插入图片描述
如图所示：将每层的元素从左至右加入队列，取出时就会先取出左节点，并将当前节点的左右节点又加入队尾，接着从队列取出下一个元素，将它的左右节点同样加入队尾，以此类推。那怎么确认取出多少个元素的时候可认为当前层的元素都取完了呢？这就需要一个变量来记录啦，这个变量其实就是每轮循环开始时队列的长度，当前长度就是当前层的所有元素，该轮循环的后续操作就是将下一层的所有节点加入队尾。

这样就实现了层序从左到右遍历二叉树。

代码如下：这份代码也可以作为二叉树层序遍历的模板，打十个就靠它了。

Go代码如下

102. 二叉树的层序遍历

迭代法

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func levelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}res := make([][]int,0)queue := make([]*TreeNode,0)queue = append(queue,root)for len(queue) != 0 {// 当前层的元素个数，以及定义存当前层结果的数组queueSize := len(queue)curLevelRes := make([]int,0)// 取出当前层所有元素，并依次加入下一层的元素for i := 0; i < queueSize ;i++ {curNode := queue[0]queue = queue[1:len(queue)]curLevelRes = append(curLevelRes,curNode.Val)// 当前节点的左右节点加入队列if curNode.Left != nil {queue = append(queue,curNode.Left)}if curNode.Right != nil {queue = append(queue,curNode.Right)}}// 当前层遍历完成，将当前层结果加入最终结果中res = append(res,curLevelRes)}return res
}

递归法

// 层序遍历递归法
func levelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}res := make([][]int,0)preOrder(root,0,&res) //根节点在第0层return res
}/*直接使用二叉树的前序遍历的递归形式即可，只是递归的时候，要多传一个参数，就是该节点属于第几层的，很简单，子节点所在层数是父节点所在层数加一*/
func preOrder(node *TreeNode,level int,res *[][]int) {//如果level是新层，则在res中继续添加一个[]int用于存这一次的结点的值if len(*res) == level {culLevelRes := make([]int,0)*res = append(*res,culLevelRes)}//将结点的值添加到res中对应的层的[]int中(*res)[level] = append((*res)[level],node.Val)//递归遍历左右子节点if node.Left != nil {preOrder(node.Left,level + 1,res)}if node.Right != nil {preOrder(node.Right,level + 1,res)}
}

在这里插入图片描述

102. 二叉树的层序遍历

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

示例 1：
在这里插入图片描述

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

Go 代码迭代法

/*** Definition for a binary tree node.* type TreeNode struct {*     Val int*     Left *TreeNode*     Right *TreeNode* }*/
func levelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}res := make([][]int,0)queue := make([]*TreeNode,0)queue = append(queue,root)for len(queue) != 0 {// 当前层的元素个数，以及定义存当前层结果的数组queueSize := len(queue)curLevelRes := make([]int,0)// 取出当前层所有元素，并依次加入下一层的元素for i := 0; i < queueSize ;i++ {curNode := queue[0]queue = queue[1:len(queue)]curLevelRes = append(curLevelRes,curNode.Val)// 当前节点的左右节点加入队列if curNode.Left != nil {queue = append(queue,curNode.Left)}if curNode.Right != nil {queue = append(queue,curNode.Right)}}// 当前层遍历完成，将当前层结果加入最终结果中res = append(res,curLevelRes)}return res
}

在这里插入图片描述

Go代码递归法

// 层序遍历递归法
func levelOrder(root *TreeNode) [][]int {if root == nil {return [][]int{}}res := make([][]int,0)preOrder(root,0,&res) //根节点在第0层return res
}/*直接使用二叉树的前序遍历的递归形式即可，只是递归的时候，要多传一个参数，就是该节点属于第几层的，很简单，子节点所在层数是父节点所在层数加一*/
func preOrder(node *TreeNode,level int,res *[][]int) {//如果level是新层，则在res中继续添加一个[]int用于存这一次的结点的值if len(*res) == level {culLevelRes := make([]int,0)*res = append(*res,culLevelRes)}//将结点的值添加到res中对应的层的[]int中(*res)[level] = append((*res)[level],node.Val)//递归遍历左右子节点if node.Left != nil {preOrder(node.Left,level + 1,res)}if node.Right != nil {preOrder(node.Right,level + 1,res)}
}