## Tree - 103. Binary Tree Zigzag Level Order Traversal

Published on with 0 views and 0 comments

103. Binary Tree Zigzag Level Order Traversal

Given a binary tree, return the zigzag level order traversal of its nodes' values. (ie, from left to right, then right to left for the next level and alternate between).

For example:
Given binary tree `[3,9,20,null,null,15,7]`,

``````    3
/ \
9  20
/  \
15   7

``````

return its zigzag level order traversal as:

``````[
[3],
[20,9],
[15,7]
]
``````

go：

``````/**

* Definition for a binary tree node.
* type TreeNode struct {
*     Val int
*     Left *TreeNode
*     Right *TreeNode
* }
*/
func zigzagLevelOrder(root *TreeNode) [][]int {
var (
res [][]int
level []int

curQ = []*TreeNode{root}
nextQ []*TreeNode
reverse = false
)

if root == nil {
return res
}

for len(curQ) != 0 {
for len(curQ) != 0 {
var cur *TreeNode
cur = curQ[0]
curQ = curQ[1:]

level = append(level, cur.Val)

if cur.Left != nil {
nextQ = append(nextQ, cur.Left)
}

if cur.Right != nil {
nextQ = append(nextQ, cur.Right)
}
}
if reverse {
var out []int
for i := len(level) -1; i >= 0; i-- {
out = append(out, level[i])
}
level = out
}

res = append(res, level)
level= nil

curQ = nextQ
nextQ = nil

if reverse {
reverse = false
} else {
reverse = true
}
}

return res
}
``````