Обход дерева зигзагом

/**
 * public class TreeNode {
 *     public int val;
 *     public TreeNode left;
 *     public TreeNode right;
 *     public TreeNode(int val, TreeNode left=null, TreeNode right=null) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */

public class Solution
{
    private static void Preorder(TreeNode node, int level, List<List<int>> output)
    {
        if (node == null)
        {
            return;
        }
        if (output.Count == level)
        {
            output.Add(new List<int>());
        }

        // делаем preorder обход и добавляем вершину на текущий уровень в конец списка
        output[level].Add(node.val);
        
        Preorder(node.left, level + 1, output);
        Preorder(node.right, level + 1, output);
    }

    public static List<List<int>> ZigzagLevelOrder(TreeNode root)
    {
        List<List<int>> output = new List<List<int>>();
        Preorder(root, 0, output);
        // Разворачиваем массивы на нечётных уровнях
        for (int i = 1; i < output.Count; i += 2)
        {
            int l = 0;
            int r = output[i].Count - 1;

            while (l < r)
            {
                int temp = output[i][l];
                output[i][l] = output[i][r];
                output[i][r] = temp;
                l++;
                r--;
            }
        }
        return output;
    }
}

#include <vector>
#include <algorithm>

using namespace std;

// struct TreeNode {
//     int val;
//     TreeNode *left;
//     TreeNode *right;
//     TreeNode(int a) : val(a), left(nullptr), right(nullptr) {}
//     TreeNode() : TreeNode(0) {}
// };

void preorder(TreeNode* node, int level, vector<vector<int>>& output) {
    if (node == nullptr) {
        return;
    }
    if (output.size() == level) {
        output.push_back({});
    }

    // делаем preorder обход и добавляем вершину на текущий уровень в конец списка
    output[level].push_back(node->val);
    
    preorder(node->left, level + 1, output);
    preorder(node->right, level + 1, output);
}

vector<vector<int>> zigzagLevelOrder(TreeNode* root) {
    vector<vector<int>> output;
    preorder(root, 0, output);
    // разворачиваем массивы на нечетных уровнях
    for (int i = 1; i < output.size(); i += 2) {
        // разворачиваем i-ый массив
        int l = 0;
        int r = output[i].size() - 1;

        while (l < r) {
            std::swap(output[i][l], output[i][r]);
            l++;
            r--;
        }
    }
    return output;
}

package main

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

func preorder(root *TreeNode, level int, levels *[][]int) {
    if root == nil {
        return
    }

    // работаем с ответом для уровня level
    if len(*levels) == level {
        *levels = append(*levels, []int{})
    }
    (*levels)[level] = append((*levels)[level], root.Val)

    // обходим левое и правое поддерево
    preorder(root.Left, level + 1, levels)
    preorder(root.Right, level + 1, levels)
}

func zigzagLevelOrder(root *TreeNode) [][]int {
    var levels [][]int
    preorder(root, 0, &levels)
    // разворачиваем массивы на нечетных уровнях
    for i := 1; i < len(levels); i += 2 {
        // разворачиваем i-ый массив
        l, r := 0, len(levels[i]) - 1
        for l < r {
            levels[i][l], levels[i][r] = levels[i][r], levels[i][l]
            l++
            r--
        }
    }
    return levels
}

import java.util.*;

// class TreeNode {
//     int val;
//     TreeNode left, right;
//     public TreeNode(int value) {
//         this.val = value;
//         this.left = this.right = null;
//     }
// }

class Solution {
    private void preorder(TreeNode node, Integer level, List<List<Integer>> levels) {
        if (node == null) {
            return;
        }

        // работаем с ответом для уровня level
        if (levels.size() == level) {
            levels.add(new ArrayList<>());
        }
        levels.get(level).add(node.val);

        // обходим левое и правое поддерево
        preorder(node.left, level + 1, levels);
        preorder(node.right, level + 1, levels);
    }

    public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<List<Integer>>();
        preorder(root, 0, levels);
        // каждый нечетный уровень разворачиваем
        for (int i = 1; i < levels.size(); i += 2) {
            Collections.reverse(levels.get(i));
        }
        return levels;
    }
}

from typing import *
from tree_node import TreeNode

# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right

def preorder(node: TreeNode, level: int, levels: List[List[int]]):
    if node is None:
        return

    # работаем с ответом для уровня level
    if level == len(levels):
        levels.append([])
    levels[level].append(node.val)

    # обходим левое и правое поддерево
    preorder(node.left, level + 1, levels)
    preorder(node.right, level + 1, levels)

def zigzag_level_order(root: TreeNode) -> List[List[int]]:
    levels = []
    preorder(root, 0, levels)
    # каждый нечетный уровень разворачиваем
    for i in range(1, len(levels), 2):
        levels[i].reverse()
    return levels

/*
class TreeNode {
    constructor(value) {
        this.val = value;
        this.left = null;
        this.right = null;
    }
}
*/

export function preorder(node, level, output) {
    if (node === null) {
        return;
    }
    if (output.length === level) {
        output.push([]);
    }

    // делаем preorder обход и добавляем вершину на текущий уровень в конец списка
    output[level].push(node.val);
    
    preorder(node.left, level + 1, output);
    preorder(node.right, level + 1, output);
}

export function zigzagLevelOrder(root) {
    const output = [];
    preorder(root, 0, output);
    // разворачиваем массивы на нечетных уровнях
    for (let i = 1; i < output.length; i += 2) {
        // разворачиваем i-ый массив
        let l = 0;
        let r = output[i].length - 1;

        while (l < r) {
            [output[i][l], output[i][r]] = [output[i][r], output[i][l]];
            l++;
            r--;
        }
    }
    return output;
}