Замените каждый узел в заданном N-арном дереве суммой всех его поддеревьев.

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

Примеры

Input:            1
                   /  |  
                2   3    4
             /      
          5     6     7
Output: Initial Pre-order Traversal: 1 2 5 6 7 3 4
              Final Pre-order Traversal: 28 20 5 6 7 3 4 
Explanation: Value of each node is replaced by the sum of all its subtrees and the node itself. 

Input:            1
                   /  |  
                4    2   3
              /            
           7     6           5
Output: Initial Pre-order Traversal: 1 4 7 6  3 5
              Final Pre-order Traversal: 23 13 7 6 28 5

Подход: эту проблему можно решить с помощью рекурсии. Выполните следующие шаги, чтобы решить данную проблему.

• Самый простой способ решить эту проблему — использовать рекурсию .
• Начните с базового условия, когда текущий узел равен NULL , затем верните 0 , так как это означает, что это конечный узел.
• В противном случае выполните рекурсивный вызов всех его дочерних узлов, обходя их с помощью цикла и добавляя в него сумму всех дочерних узлов .
• Наконец верните данные текущего узла.
• Таким образом, все значения узла будут заменены суммой всех поддеревьев и самого себя.

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

Временная сложность: O(N), где N — количество узлов в дереве.