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

## 1. 题目 ### **描述** 给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替） 数据范围：0≤*n*≤1500,树上每个节点的val满足 |val| <= 1500 要求：空间复杂度：O*(*n)，时间复杂度：O(n) 例如： 给定的二叉树是{1,2,3,#,#,4,5}  该二叉树之字形层序遍历的结果是 [ [1], [3,2], [4,5] ] ### **示例1** 输入： ```csharp {1,2,3,#,#,4,5} ``` 返回值： ```csharp [[1],[3,2],[4,5]] ``` 说明： ```csharp 如题面解释，第一层是根节点，从左到右打印结果，第二层从右到左，第三层从左到右。 ``` ### **示例2** 输入： ```csharp {8,6,10,5,7,9,11} ``` 返回值： ```csharp [[8],[10,6],[5,7,9,11]] ``` ### **示例3** 输入： ```csharp {1,2,3,4,5} ``` 返回值： ```csharp [[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. 编码实现 核心代码如下： ```csharp /** * * @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