103. 二叉树的锯齿形层序遍历

题目

给你二叉树的根节点 root ，返回其节点值的 锯齿形层序遍历 。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

难度：🌟🌟🌟

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解

和层序遍历一样，只不过加了是否逆序的标识位。

代码实现

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}
	var res [][]int
	queue := newQueue()
	queue.offer(root)
	leftToRight := true
	for !queue.isEmpty() {
		sz := queue.len()
		var ans []int
		for sz > 0 {
			// 弹出队头元素
			top := queue.pop()
			ans = append(ans, top.Val)
			if top.Left != nil {
				queue.offer(top.Left)
			}
			if top.Right != nil {
				queue.offer(top.Right)
			}
			sz--
		}
		var arr []int
		if leftToRight { // 从左向右
			for i := 0; i < len(ans); i++ {
				arr = append(arr, ans[i])
			}
		} else {
			for i := len(ans) - 1; i >= 0; i-- {
				arr = append(arr, ans[i])
			}
		}
		leftToRight = !leftToRight
		res = append(res, arr)
	}
	return res
}

type myQueue struct {
	data []*TreeNode
}

func newQueue() *myQueue {
	return &myQueue{}
}

func (q *myQueue) offer(elem *TreeNode) {
	q.data = append(q.data, elem)
}

func (q *myQueue) pop() *TreeNode {
	res := q.data[0]
	q.data = q.data[1:]
	return res
}

func (q *myQueue) len() int {
	return len(q.data)
}

func (q *myQueue) isEmpty() bool {
	return q.len() == 0
}