Обход по уровням

/**
 * 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>> LevelOrderTraversal(TreeNode root)
    {
        var output = new List<List<int>>();
        Preorder(root, 0, output);
        return output;
    }
}

#include <vector>

using namespace std;

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

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>> levelOrderTraversal(TreeNode* root) {
    vector<vector<int>> output;
    preorder(root, 0, output);
    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 levelOrderTraversal(root *TreeNode) [][]int {
    var levels [][]int
    preorder(root, 0, &levels)
    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>> levelOrderTraversal(TreeNode root) {
        List<List<Integer>> levels = new ArrayList<List<Integer>>();
        preorder(root, 0, levels);
        return levels;
    }
}

from typing import *

# 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 level_order_traversal(root: TreeNode) -> List[List[int]]:
    result = []
    preorder(root, 0, result)
    return result

/*
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 levelOrderTraversal(root) {
    const output = [];
    preorder(root, 0, output);
    return output;
}