В динамике по поддеревьям мы обрабатываем вершины в "порядке обхода в глубину". Обходя дерево в глубину, мы попутно считаем значение динамики, используя значения поддеревей детей, которые мы уже посчитали в процессе обхода.
Для примера решим следующую задачу. Дано бинарное дерево (у каждой вершины не больше двух детей), у которого каждая вершина имеет вес (возможно отрицательный). Весом пути в дереве будем называть сумму весов вершин, содержащихся в этом пути. Необходимо найти значение максимального веса простого пути в этом дереве.
Для начала подвесим дерево за какую-нибудь вершину (например за вершину с номером 1).
Будем рассматривать два типа путей:
1) Вертикальные пути - один из концов пути является предком второго конца.
2) Горизонтальные пути - ни один из концов пути не является предком второго.
Любой путь в дереве относится к одному из этих типов.
У каждого горизонтального пути есть высшая точка, которая является наименьшим общим предком двух концов этого пути. Для вертикального пути высшей точкой является просто конец-предок.
Чтобы рассмотреть все возможные пути будем перебирать высшие точки путей. Допустим мы зафиксировали некоторую вершину. Если это высшая точка некоторого вертикального пути, то второй конец - это вершина, которая лежит где-то в поддереве зафиксированной вершины. Если же это высшая точка горизонтального пути, то первый конец пути лежит в поддереве левого ребенка, а другой конец лежит в поддереве правого ребенка (а иначе вершина v на самом деле не является высшей точкой). Будем пользоваться этим, чтобы вычислять оптимальные пути.
Для решения воспользуемся динамическим программированием: dp[v] - значение максимального веса
вертикального пути с высшей точкой в вершине v.
Подсчет dp[v] - есть три способа построить оптимальный вертикальный путь с высшей точкой в вершине v:
1) Путь, который состоит только из вершины v. Тогда вес равен просто весу вершины v. Это можно использовать как начальное значение динамики.
2) Взять оптимальный вертикальный путь с высшей точкой в левом ребенке и продлить его вершиной v. Значение такого пути равно dp[left] + w(v).
3) Взять оптимальный вертикальный путь с высшей точкой в правом ребенке и продлить его вершиной v. Значение такого пути равно dp[right] + w(v).
Если взять максимальное значение dp[v], то узнаем максимальный вес вертикальных путей.
Осталось учесть горизонтальные пути. Их также можно считать при помощи dp. Зафиксировав вершину v как высшую точку горизонтальных путей, нужно просто взять значение dp[left] + w(v) + dp[right], так как в высшей точке просто соединяются два вертикальных пути из разных поддеревьев. Учитывая эти значения при всех v, мы можем определить максимальный вес среди всех путей.
Реализовать это все можно через обход дерева в глубину. Подробнее в коде:
// Структура для хранения бинарного дерева
struct TreeNode {
int val;
TreeNode* left;
TreeNode* right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode* left, TreeNode* right) : val(x), left(left), right(right) {}
};
// глобальный ответ - значение максимального пути
int res;
// dp[v] - значение максимального пути,
// у которого высшая вершина v, а нижняя где-то в поддереве вершины v
// вместо того, чтобы хранить массив dp
// будем просто возвращать его в качестве значения рекурсии (обхода в глубину)
int calc(TreeNode* v) {
// vert - вертикальный путь из вершины v, фактически - значение dp[v]
// начальное значение - значение в вершине v, то есть путь только из вершины v
int vert = v->val;
// hor - горизонтальный путь, у котого высшая точка (lca) это вершина v
// инициализируем значением в вершине v
int hor = v->val;
// если левый ребенок существует
if (v->left != nullptr) {
int d = calc(v->left); // посчитали значение динамики у левого ребенка
vert = max(vert, d + v->val); // обновляем вертикальный путь как продолжение пути левого ребенка
hor += d; // добавляем левую ветвь горизонтального пути
}
// если правый ребенок существует
if (v->right != nullptr) {
int d = calc(v->right); // посчитали значение динамики у левого ребенка
vert = max(vert, d + v->val); // обновляем вертикальный путь как продолжение пути правого ребенка
hor += d; // добавляем правую ветвь горизонтального пути
}
// обновляем глобальный ответ через вертикальный путь с высшей точкой в v
res = max(res, vert);
// обновляем глобальный ответ через горизонтальный путь с высшей точкой (lca) в v
res = max(res, hor);
// возвращаем значение динамики вершины v
return vert;
}
int maxPathSum(TreeNode* root) {
// изначальное максимальное значение равно нулю - пустой путь, не содержащий вершин
res = 0;
// запускаем обход в глубину
calc(root);
// теперь у res актуальное значение
return res;
}