Binary Tree Zigzag Level Order Traversal

1. Problem Description

Given the root root of a binary tree, return the zigzag level-order traversal of its node values (left to right on one level, then right to left on the next, alternating between levels).

2. Approach

1. Perform level-order traversal, then reverse every other level

3. Implementation

/**
 * 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. References

• 103. Binary Tree Zigzag Level Order Traversal - LeetCode