[数据结构与算法]每日一题---剑指 Offer 32 - III. 从上到下打印二叉树 III[力扣][Go]

题目描述

请实现一个函数按照之字形顺序打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。

解题代码

// 利用顺序表做，不递归
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
}

也可以利用链表进行前插和后插的交替来模拟队列完成，我懒就不写了。

提交结果