103. 二叉树的锯齿形层序遍历
https://leetcode.cn/problems/binary-tree-zigzag-level-order-traversal/
给你二叉树的根节点 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
解题思路
就是层序遍历的思路，做个小变种
代码
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return [][]int{}
}
var res [][]int
q := []*TreeNode{root}
for len(q) > 0 {
var tmp []*TreeNode
var data []int
for len(q) > 0 {
tail := q[len(q)-1]
q = q[:len(q)-1]
data = append(data, tail.Val)
if tail.Left != nil {
tmp = append(tmp, tail.Left)
}
if tail.Right != nil {
tmp = append(tmp, tail.Right)
}
}
if len(data) > 0 {
res = append(res, data)
}
q = tmp
tmp = make([]*TreeNode, 0)
data = make([]int, 0)
for len(q) > 0 {
tail := q[len(q)-1]
q = q[:len(q)-1]
data = append(data, tail.Val)
if tail.Right != nil {
tmp = append(tmp, tail.Right)
}
if tail.Left != nil {
tmp = append(tmp, tail.Left)
}
}
q = tmp
if len(data) > 0 {
res = append(res, data)
}
}
return res
}