二叉树的锯齿型层次遍历

二叉树的锯齿形层次遍历是指从左到右和从右到左交替进行的层次遍历。在锯齿形层次遍历中，奇数层从左到右遍历，偶数层从右到左遍历。以下是一个用 Golang 实现的例子：

package main

import "fmt"

func sum(nums []int) int {
    result := 0
    for _, num := range nums {
        result += num
    }
    return result
}

func main() {
    numbers := []int{1, 2, 3, 4, 5}
    total := sum(numbers)
    fmt.Printf("数组 %v 的和是 %d\n", numbers, total)
}

package main

import (
	"fmt"
)

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	if root == nil {
		return nil
	}

	result := [][]int{}
	queue := []*TreeNode{root}
	level := 0

	for len(queue) > 0 {
		levelSize := len(queue)
		currentLevel := make([]int, levelSize)

		for i := 0; i < levelSize; i++ {
			node := queue[0]
			queue = queue[1:]

			// 根据当前层的奇偶性判断插入顺序
			if level%2 == 0 {
				currentLevel[i] = node.Val
			} else {
				currentLevel[levelSize-i-1] = node.Val
			}

			// 将左右子节点加入队列
			if node.Left != nil {
				queue = append(queue, node.Left)
			}
			if node.Right != nil {
				queue = append(queue, node.Right)
			}
		}

		result = append(result, currentLevel)
		level++
	}

	return result
}

func main() {
	// 创建一个二叉树
	root := &TreeNode{Val: 3}
	root.Left = &TreeNode{Val: 9}
	root.Right = &TreeNode{Val: 20}
	root.Right.Left = &TreeNode{Val: 15}
	root.Right.Right = &TreeNode{Val: 7}

	// 进行锯齿形层次遍历
	result := zigzagLevelOrder(root)

	// 输出结果
	fmt.Println(result)
}