题目

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

例如:

给定二叉树: [3,9,20,null,null,15,7],

    3
   / \
  9  20
    /  \
   15   7

返回其层次遍历结果：
[
  [3],
  [20,9],
  [15,7]
]

题解

剑指 Offer 32 - I. 从上到下打印二叉树：打印结果直接保存

剑指 Offer 32 - II. 从上到下打印二叉树 II：打印结果分层保存

本题是从上到下打印二叉树的最终篇：根据奇偶层决定打印顺序

• 初始化结果数组res为空，初始化辅助队列queue为root节点

• 循环执行：新建本层结果tmp
• 因为奇偶层打印顺序不同，要求tmp支持从头尾进行写入，可以使用双端队列
• 奇数层：从tmp尾部写入
• 偶数层：从tmp头部写入

• 记录当前queue节点数量n，执行n次出队操作
• 出队时，将当前节点val写入tmp，叶子节点根据奇偶层写入tmp
• 本层打印完毕时，tmp写入res

• queue为空时，循环结束

代码

func levelOrder(root *TreeNode) [][]int {
	// 特殊场景：根节点为nil时，返回空数组
	if root == nil {
		return [][]int{}
	}
	// 初始化辅助队列
	var queue []*TreeNode = []*TreeNode{root}
	// 初始化结果数组
	res := make([][]int, 0)
	// 初始化层数
	height := 1
	// queue为空时，退出循环
	for len(queue) > 0 {
		// 新建本层结果数组
		tmp := make([]int, 0)
		// 记录当前本层节点数量
		size := len(queue)
		// 记录本层结果
		for i := 0; i < size; i++ {
			// 出队
			node := queue[0]
			queue = queue[1:]
			// 根据奇偶层，选择写入顺序
			if height%2 == 0 {
				// 偶数层：从头部写入
				tmp = append([]int{node.Val}, tmp...)
			} else {
				// 奇数层：从尾部写入
				tmp = append(tmp, node.Val)
			}
			// 写入出队节点子节点
			if node.Left != nil {
				queue = append(queue, node.Left)
			}

			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}
		// 层数+1
		height++
		// 本层结果写入结果数组
		res = append(res, tmp)
	}
	return res
}