前言
中间又断更新。
正文
问题来源
本问题来自leetcode上的103题。
问题描述
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
示例 1:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
示例 2:
[
[3],
[20,9],
[15,7]
]
分析：
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
type node struct {
level int
tn *TreeNode
}
func reverse(slice []int) {
i := 0
j := len(slice) - 1
for i < j {
slice[i], slice[j] = slice[j], slice[i]
i++
j--
}
}
func zigzagLevelOrder(root *TreeNode) [][]int {
if root == nil {
return nil
}
ret := make([][]int, 0)
queue := append([]node{}, node{level:0,tn:root})
curLevel := 0
var r []int
for len(queue) != 0 {
p := queue[0]
queue = queue[1:]
if p.level != curLevel {
if curLevel%2 == 1 {
reverse(r)
}
curLevel++
ret = append(ret, r)
r = append([]int{}, p.tn.Val)
} else {
r = append(r, p.tn.Val)
}
if p.tn.Left != nil {
queue = append(queue, node{level:curLevel+1,tn:p.tn.Left})
}
if p.tn.Right != nil {
queue = append(queue, node{level:curLevel+1,tn:p.tn.Right})
}
}
if curLevel%2 == 1 {
reverse(r)
}
ret = append(ret, r)
return ret
}
总结：
勤思考。
结语
不管怎么样好好加油。
