二叉树的锯齿形层序遍历。给定一个二叉树，返回其节点值的锯齿形层序遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。力扣103。
自然智慧即可。层次遍历。
时间复杂度：O(N)。
空间复杂度：O(N)。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
head := &TreeNode{}
head.val = 3
head.left = &TreeNode{}
head.left.val = 9
head.right = &TreeNode{}
head.right.val = 20
head.right.left = &TreeNode{}
head.right.left.val = 15
head.right.right = &TreeNode{}
head.right.right.val = 7
ret := zigzagLevelOrder(head)
fmt.Println(ret)
}
type TreeNode struct {
val int
left *TreeNode
right *TreeNode
}
func zigzagLevelOrder(root *TreeNode) [][]int {
ans := make([][]int, 0)
if root == nil {
return ans
}
deque := make([]*TreeNode, 0)
deque = append(deque, root)
size := 0
isHead := true
for len(deque) > 0 {
size = len(deque)
curLevel := make([]int, 0)
for i := 0; i < size; i++ {
var cur *TreeNode
if isHead {
cur = deque[0]
deque = deque[1:]
} else {
cur = deque[len(deque)-1]
deque = deque[0 : len(deque)-1]
}
curLevel = append(curLevel, cur.val)
if isHead {
if cur.left != nil {
deque = append(deque, cur.left)
}
if cur.right != nil {
deque = append(deque, cur.right)
}
} else {
if cur.right != nil {
deque = append([]*TreeNode{cur.right}, deque...)
}
if cur.left != nil {
deque = append([]*TreeNode{cur.left}, deque...)
}
}
}
ans = append(ans, curLevel)
isHead = !isHead
}
return ans
}执行结果如下：
