Количество поддеревьев с суммой цифр всех узлов, равной X

Опубликовано: 20 Сентября, 2022

Дано бинарное дерево, состоящее из N узлов и положительного целого числа X . Задача состоит в том, чтобы подсчитать количество поддеревьев с суммой цифр вершин, равной X .

Примеры:

Input: N = 7, X = 29

           10
          /    
       2       3
     /       /  
   9    3  4   7

Output: 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   7

Output: 2

Подход: эта задача представляет собой вариант подсчета поддеревьев в бинарном дереве с заданной суммой. Чтобы решить эту проблему, замените все узлы их суммами цифр, используя любой обход дерева, а затем подсчитайте поддеревья с суммой X.

Ниже приведена реализация описанного выше подхода.

Временная сложность: O(N).
Вспомогательное пространство: O(1).

РЕКОМЕНДУЕМЫЕ СТАТЬИ