图解算法：按之字形顺序打印二叉树（ Z字形、锯齿形遍历）

1. 题目

描述

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 数据范围：0≤*n≤1500,树上每个节点的val满足 |val| <= 1500 要求：空间复杂度：O(*n)，时间复杂度：O(n) 例如： 给定的二叉树是{1,2,3,#,#,4,5} 该二叉树之字形层序遍历的结果是 [ [1], [3,2], [4,5] ]

示例1

输入：

{1,2,3,#,#,4,5}

返回值：

[[1],[3,2],[4,5]]

说明：

如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。     

示例2

输入：

{8,6,10,5,7,9,11}

返回值：

[[8],[10,6],[5,7,9,11]]

示例3

输入：

{1,2,3,4,5}

返回值：

[[1],[3,2],[4,5]]

2. 解题思路

对于二叉树的按之字形（ 锯齿形）遍历，可以这样操作：先将二叉树进行层序遍历，对于层序遍历的结果进行处理（第2层、第4次、第6层等偶数层的数据进行翻转）。 因此本题的难点还是实现二叉树的层序遍历。 二叉树的层序遍历具体实现如下： 二叉树的层序遍历可以通过【队列】辅助完成，假如要遍历的二叉树如下图所示： 可以通过以下步骤完成层序遍历： 步骤一：定义一个队列，保存每一层的所有节点；先将根节点放入队列。 定义一个队列，初始化时将二叉树的根节点添加进去，此时队列只有一个数据，即count=1。 步骤二：执行出队列操作：出队列的左右子树再重新入队列。出队列的顺序就是二叉树层序遍历的顺序。 之后将队列中的3出队列，只出一个数据（因为此时的count==1）。之后再将3的左右子树入队列。 这时，队列中就有2个数据了，count2。接下来出队列2个数据（因为count2）。即将5和1出队列，同时将5和1的左右子树入队列。 这时，队列中就有4个数据了，count4。接下来出队列4个数据（因为count4）。即将6、2、0、和8出队列，同时将2的左右子树入队列（其他节点不用，因为节点的左右子树已经为Null）。 这时，队列中就有2个数据了，count2。接下来出队列2个数据（因为count2）。即将7和4出队列，7和4的左右子树都为Null了，就不再入队列。 到此时，队列为空，二叉树的层序遍历完成。将结果集返回。 如果文字描述的不太清楚，你可以参考视频的详细讲解。

• Python版本：https://www.bilibili.com/cheese/play/ep1371669

• Java版本：https://www.bilibili.com/cheese/play/ep1367108

• Golang版本：https://www.bilibili.com/cheese/play/ep1364648

  3. 编码实现

  核心代码如下：

/**
 *
 * @param root TreeNode类
 * @return int整型二维数组
 */
func zigzagLevelOrder(root *TreeNode) [][]int {// write code hereres := make([][]int, 0) //返回最终结果变量level := 1              //二叉树的层if root == nil {	return res}queue := []*TreeNode{root} //定义一个队列，保存每一层的所有节点；先将根节点放入队列
for len(queue) > 0 {	row := make([]int, 0) //保存 当前层（每一层）的节点	count := len(queue)   //获取一层中的节点数量，并进行遍历//如果当前层有节点，将节点数据添加到数组中，左、右子树添加到队列中	for i := 0; i < count; i++ {		node := queue[0]            //获取队列的顶部元素		queue = queue[1:]           //删除队列的顶部元素		row = append(row, node.Val) //节点值添加到切片中	//若是左右子节点存在，则存入左右节点作为下一个层次		if node.Left != nil {			queue = append(queue, node.Left)		}		if node.Right != nil {			queue = append(queue, node.Right)		}}if level%2 == 0 {		reverseSlice(row) //偶数行反转，逆序排列	}	res = append(res, row) //一层结束，将这一层的数据追加到结果变量中	level++
}return res
}
// reverseStrings 翻转一个字符串切片
func reverseSlice(row []int) {for i, j := 0, len(row)-1; i < j; i, j = i+1, j-1 {	row[i], row[j] = row[j], row[i]}
}

具体完整代码你可以参考下面视频的详细讲解。

• Python版本：https://www.bilibili.com/cheese/play/ep1371669

• Java版本：https://www.bilibili.com/cheese/play/ep1367108

• Golang版本：https://www.bilibili.com/cheese/play/ep1364648

  4.小结

  二叉树的按之字形（ Z字形、锯齿形）遍历，可以这样操作：先将二叉树进行层序遍历，对于层序遍历的结果进行处理（第2层、第4次、第6层等偶数层的数据进行翻转）。 《数据结构与算法》深度精讲课程正式上线啦！七大核心算法模块全解析： ✅ 链表 ✅ 二叉树 ✅二分查找、排序 ✅ 堆、栈、队列 ✅回溯算法 ✅ 哈希算法 ✅ 动态规划 无论你是备战笔试面试、提升代码效率，还是突破技术瓶颈，这套课程都将为你构建扎实的算法思维底座。🔥立即加入学习打卡，与千名开发者共同进阶！

• Python编码实现：https://www.bilibili.com/cheese/play/ss897667807

• Java编码实现：https://www.bilibili.com/cheese/play/ss161443488

• Golang编码实现：https://www.bilibili.com/cheese/play/ss63997