Поддеревья высоты h в бинарном дереве

Во-первых, мы рекурсивно вычисляем высоту дерева следующим образом:

Если дерево пусто, высота равна 0.

Если дерево не пусто, высота равна максимальной высоте его дочерних элементов плюс 1.

В C (я предполагаю, что OP использует C на основе ответа), это выглядит так

typedef struct Node {
    Node* leftChild,
    node* rightChild
} Node;

typedef Node* Tree;

unsigned int max(unsigned int a, unsigned int b) {
    return a > b ? a : b;
}

unsigned int height(Tree tree) {
    return tree ? 1 + max(height(tree->leftChild, tree->rightChild)) : 0;
}

Обратите внимание, что обычно Node будет иметь некоторые дополнительные данные. Но эти данные здесь неуместны, поэтому мы их не включаем (хотя при желании это можно сделать достаточно легко).

Теперь мы хотим немного изменить функцию height. Для этого определим

typdef struct Result {
    unsigned int height,
    unsigned int count
} Result;

/**
 * The returned .height should be the height of the tree.
 * The returned .count should be the number of subtrees of tree
 * with height k.
*/
Result resultCountChildren(Tree tree, unsigned int k) {
    if (tree) {
        Result leftResult = resultCountChildren(tree->left, k);
        Result rightResult = resultCountChildren(tree->right, k);
        unsigned int heightOfTree = 1 + max(leftResult.height, rightResult.height);
        unsigned int count = leftResult.count + rightResult.count + (heightOfTree == k);
        Result result = {
            .height = heightOfTree,
            .count = count
        };
        return result;
    } else {
        unsigned int height = 0;
        unsigned int count = (0 == k);
        Result result = {
            .height = height,
            .count = count
        };
        return result;
    }
}

unsigned int count(Tree tree, unsigned int k) {
    return resultCountChildren(tree).count;
}