103 二叉树的锯齿形层序遍历

题目描述#

给你二叉树的根节点 root，返回其节点值的锯齿形层序遍历结果。即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行。

思路#

在 102 题层序遍历的基础上加一个方向判断。用 height 记录当前层数（从 0 开始），偶数层从左往右正常追加，奇数层从右往左，只需在每层处理完后判断 height%2 == 1，对结果翻转即可。

翻转使用标准库 slices.Reverse，只作用于当前层的切片，不影响其他层。

根节点为空时直接返回空数组，不进入循环。

代码#

import "slices"

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) (ans [][]int) {
    // 0. root 为nil
    if root == nil {
        return [][]int{}
    }
    // 1. 使用队列保存每一行的数据
    queue := []*TreeNode{root}
    height := 0 // height表示二叉树的层数
    for len(queue) > 0 {
        queueSize := len(queue)
        ans = append(ans, []int{})
        // 2. 使用正常的层序遍历
        for i := 0; i < queueSize; i++ {
            node := queue[0]
            queue = queue[1:]
            ans[height] = append(ans[height], node.Val)
            if node.Left != nil {
                queue = append(queue, node.Left)
            }
            if node.Right != nil {
                queue = append(queue, node.Right)
            }
        }
        // 3. 如果当前为奇数层，我们需要翻转当前的层数ans即可
        if height%2 == 1 {
            slices.Reverse(ans[height])
        }
        height++
    }
    return
}