Количество поддеревьев с суммой цифр всех узлов, равной X
Дано бинарное дерево, состоящее из N узлов и положительного целого числа X . Задача состоит в том, чтобы подсчитать количество поддеревьев с суммой цифр вершин, равной X .
Примеры:
Input: N = 7, X = 29
10
/
2 3
/ /
9 3 4 7Output: 2
Explanation: The whole binary tree is a subtree with digit sum equals 29.Input: N = 7, X = 14
10
/
2 3
/ /
9 3 4 7Output: 2
Подход: эта задача представляет собой вариант подсчета поддеревьев в бинарном дереве с заданной суммой. Чтобы решить эту проблему, замените все узлы их суммами цифр, используя любой обход дерева, а затем подсчитайте поддеревья с суммой X.
Ниже приведена реализация описанного выше подхода.
Временная сложность: O(N).
Вспомогательное пространство: O(1).