题目描述
请实现一个函数按照之字形顺序打印二叉树,即第一行按照从左到右的顺序打印,第二层按照从右到左的顺序打印,第三行再按照从左到右的顺序打印,其他行以此类推。
解题代码
// 利用顺序表做,不递归
func levelOrder(root *TreeNode) [][]int {
var sum [][]int
var tem []int
n := 1
var queue []*TreeNode
if root != nil {
queue = append(queue, root)
}
for len(queue) != 0 {
if n%2 == 0{
for size := len(queue) - 1; size >= 0; size-- {
node := queue[size]
tem = append(tem, node.Val)
if node.Right != nil {
queue = append(queue, node.Right)
}
if node.Left != nil {
queue = append(queue, node.Left)
}
if size == 0{
queue = queue[1:]
} else {
tem2 := queue[size+1:]
queue = queue[:size]
for _, treeNode := range tem2 {
queue = append(queue,treeNode)
}
}
}
} else {
for size := len(queue) - 1; size >= 0; size-- {
node := queue[size]
tem = append(tem, node.Val)
if node.Left != nil {
queue = append(queue, node.Left)
}
if node.Right != nil {
queue = append(queue, node.Right)
}
if size == 0{
queue = queue[1:]
} else {
tem2 := queue[size+1:]
queue = queue[:size]
for _, treeNode := range tem2 {
queue = append(queue,treeNode)
}
}
}
}
sum = append(sum, tem)
tem = []int{}
n++
}
return sum
}
也可以利用链表进行前插和后插的交替来模拟队列完成,我懒就不写了。