Подсчёт суммы значений листовых узлов бинарного дерева

Условие

Реализуйте функцию, получающую в качестве аргумента корневой узел бинарного дерева, где каждый узел хранит целое число. Функция должна вычислить и вернуть сумму всех значений, находящихся в листовых узлах (узлах без дочерних элементов).

Ответ

Лист — узел без обоих потомков. Для пустого дерева верните 0, для листа — его значение, иначе сложите результаты левого и правого поддеревьев.

long long sumLeaves(const Node* root) {
    if (!root) return 0;
    if (!root->left && !root->right) return root->value;
    return sumLeaves(root->left) + sumLeaves(root->right);
}

Предполагается Node с полями value, left и right и сумма, помещающаяся в long long. Узел с одним потомком не является листом. Время O(n), память стека O(h); для очень глубокого дерева стоит заменить рекурсию явным стеком. Отрицательные значения учитываются без специальных исключений.