Максимальная сумма пути двоичного дерева
Для непустого двоичного дерева найдите максимальную сумму путей. Для этой проблемы путь определяется как любая последовательность узлов от некоторого начального узла до любого узла в дереве вдоль соединений родитель-потомок. Путь должен содержать хотя бы один узел и не должен проходить через корень.
Решение:
Я использовал DFS, а также алгоритм поиска в глубину, чтобы решить эту проблему. Например: когда я добрался до узла (u), у которого также есть два дочерних узла, такие как x и y, я вычислил значение DP [u], в котором хранится максимальное суммирование этого поддерева, основанного на u на основе по максимальным значениям дочерних узлов. Как найти DP [u]? Итак, узел u имеет поле значения (u- ›val).
Сложность времени: O (n)
Ссылка: https://leetcode.com/problems/binary-tree-maximum-path-sum/
