# Leetcode - binary-tree-zigzag-level-order-traversal

violet posted @ Mar 14, 2020 02:23:37 AM in 胡扯 with tags Algorithm Golang BFS , 332 阅读

https://leetcode.com/problems/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]
]
```

```/**
* 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{}
}
queue := []*TreeNode{root}
result := [][]int{}
level := 0
for len(queue) != 0 {
size := len(queue)
levelResult := []int{}
for i := 0; i < size; i++ {
node := queue[i]
levelResult = append(levelResult, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
}
level++
if level%2 == 0 {
levelResult = reverse(levelResult)
}
result = append(result, levelResult)
queue = queue[size:]
}
return result
}

func reverse(nums []int) []int {
size := len(nums)
for i := 0; i < size/2; i++ {
nums[i], nums[size-1-i] = nums[size-1-i], nums[i]
}
return nums
}```

(输入验证码)
or Ctrl+Enter