#include <iostream>

const int MAX_CHILDREN = 10; // Максимальное количество дочерних узлов

struct TreeNode {
    int value;
    TreeNode* children[MAX_CHILDREN]; // Массив фиксированной длины для хранения дочерних узлов
    int childCount; // Текущая количество дочерних узлов

    TreeNode(int val) : value(val), childCount(0) {
        for (int i = 0; i < MAX_CHILDREN; ++i) {
            children[i] = nullptr; // Инициализируем дочерние узлы как пустые
        }
    }

    // Метод для добавления дочернего узла
    bool addChild(TreeNode* child) {
        if (childCount < MAX_CHILDREN) {
            children[childCount++] = child; // Добавляем дочерний узел и увеличиваем счетчик
            return true;
        }
        return false; // Если максимальное количество дочерних узлов достигнуто
    }
};

// Функция для подсчета числа листьев в поддереве
int countLeaves(TreeNode* node) {
    if (!node) return 0;  // Если узел пустой, возвращаем 0

    if (node->childCount == 0) {
        return 1;  // Если узел - лист, возвращаем 1
    }

    int totalLeaves = 0;
    for (int i = 0; i < node->childCount; ++i) {
        totalLeaves += countLeaves(node->children[i]); // Рекурсивно считаем листья в дочерних узлах
    }
    return totalLeaves;
}

// Функция для поиска самого высокого поддерева с заданным количеством листьев
TreeNode* findHighestSubtreeWithLeaves(TreeNode* node, int targetLeaves, int& maxHeight, int currentHeight) {
    if (!node) return nullptr;

    // Считаем количество листьев в текущем узле поддерева
    int leavesCount = countLeaves(node);

    // Проверяем, соответствует ли количество листьев заданному
    if (leavesCount == targetLeaves) {
        // Если это поддерево выше самого высокого найденного, обновляем
        if (currentHeight > maxHeight) {
            maxHeight = currentHeight;
            return node;  // Возвращаем данное поддерево
        }
    }

    // Рекурсивно ищем в дочерних узлах
    TreeNode* highestSubtree = nullptr;

    for (int i = 0; i < node->childCount; ++i) {
        TreeNode* result = findHighestSubtreeWithLeaves(node->children[i], targetLeaves, maxHeight, currentHeight + 1);
        if (result) {
            highestSubtree = result;  // Сохраняем найденное поддерево
        }
    }

    return highestSubtree;
}

void deleteTree(TreeNode* node) {
    if (!node) return; // Если узел пустой, выходим

    // Рекурсивно освобождаем память для дочерних узлов
    for (int i = 0; i < node->childCount; ++i) {
        deleteTree(node->children[i]);
    }

    // Освобождаем память для текущего узла
    delete node;
}

bool inputValue(int root) {
    std::cin >> root;
    if (std::cin.fail()) {
        std::cin.clear();
        std::cin.ignore(256, '\n');
        std::cout << "Wrong, try again" << std::endl;
        return false;
    }
    return true;
}

TreeNode* inputTree(int& nodeCount) {
    std::cout << "Введите значение узла (или -1 для завершения): ";
    int value;
    std::cin >> value;

    // Если введено -1, завершаем ввод
    if (value == -1) {
        return nullptr;
    }

    TreeNode* node = new TreeNode(value);
    nodeCount++; // Увеличиваем счетчик узлов

    std::cout << "Добавьте дочерние узлы для " << value << " (введите -1 для завершения): " << std::endl;
    for (int i = 0; i < MAX_CHILDREN; ++i) {
        TreeNode* child = inputTree(nodeCount); // Рекурсивно вводим дочерний узел
        if (child) {
            node->addChild(child);
        }
        else {
            break; // Если был введен -1, выходим из цикла
        }
    }

    return node;
}

int main() {
    setlocale(LC_ALL, "Russian");
    // Создаем N-дерево
    int nodeCount = 0; // Счетчик узлов
    TreeNode* root = inputTree(nodeCount); // Вводим дерево с клавиатуры
    int targetLeaves = 2;  // Заданное число листьев
    int maxHeight = -1;    // Начальная высота
    TreeNode* highestSubtree = findHighestSubtreeWithLeaves(root, targetLeaves, maxHeight, 0);

    // Выводим результат
    if (highestSubtree) {
        std::cout << "Найдено поддерево с " << targetLeaves << " листьями на высоте " << maxHeight << std::endl;
    }
    else {
        std::cout << "Не найдено поддерево с " << targetLeaves << " листьями." << std::endl;
    }

    deleteTree(root);

    return 0;
} можешь добавить создание дерева путём чтения из текстового файла