二叉树的锯齿形层序遍历

1. 题目描述

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

2. 思路

1. 层序遍历，最后翻转数组即可

3. 实现

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    if root == nil {
        return nil
    }

    queue := []*TreeNode{root}
    currentLineLast := root
    var nextLineLast *TreeNode
    var path []int
    var allPaths [][]int
    for len(queue) > 0 {
        node := queue[0]
        queue = queue[1:]
        path = append(path, node.Val)
        if node.Left != nil {
            queue = append(queue, node.Left)
            nextLineLast = node.Left
        }
        if node.Right != nil {
            queue = append(queue, node.Right)
            nextLineLast = node.Right
        }
        if node == currentLineLast {
            dst := make([]int, len(path))
            copy(dst, path)
            allPaths = append(allPaths, dst)
            path = []int{}
            currentLineLast = nextLineLast
        }
    }

    for i, path := range allPaths {
        if i%2 == 1 {
            reverse(path)
        }
    }

    return allPaths
}


func reverse(path []int){
    left := 0
    right := len(path)-1
    for left < right {
        path[left],path[right] = path[right],path[left]
        left++
        right--
    }
}

4. 参考

• 103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）