Максимизируйте сумму пути от корня до конечного узла в N-арном дереве

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

Примеры:

Input:

Output: 12
Explanation: The path sum to every leaf from the root are:
For node 4: 1 -> 2 -> 4 = 7
For node 5: 1 -> 2 -> 5 = 8
For node 6: 1 -> 3 -> 6 = 10
For node 7: 1 -> 3 -> 7 = 11
For node 8: 1 -> 3 -> 8 = 12 (maximum)

The maximum path sum is 12 i.e., from root 1 to leaf 8.

Подход: Данную проблему можно решить, выполнив обход DFS по заданному дереву. Идея состоит в том, чтобы выполнить обход DFS из корневого узла данного универсального дерева, отслеживая сумму значений узлов в каждом пути, и, если возникает какой-либо конечный узел, максимизировать значение текущей суммы пути, полученного в переменная, скажем maxSum .

После выполнения DFS Traversal выведите значение maxSum как результирующий путь максимальной суммы.

Ниже приведена реализация вышеуказанного подхода:

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