Решение задачи

Алгоритм решения задачи:

В DFS каждый раз, когда мы делаем рекурсию, мы увеличиваем уровень на единицу. Например, на пути от корня к листу с максимальным уровнем уровни (1, 2, 3, ... n). (Предположим, что n — максимальный уровень)

Тогда в вопросе на пути от корня к листу с максимальным уровнем вес равен n, n-1, n-2..., 1.

Итак, какова связь между (1, 2, 3,... n) и (n, n-1, n-2... 1). Ну, (n, n-1, n-2..., 1) можно переписать как ( (n+1)-1, (n+1)-2, (n+1)-3,... ( п+1)-п).

Совершенно очевидно, что мы можем добавить вес (n+1) для каждого значения узла (flatSum * (max + 1)), и вычесть (1, 2, 3, ... n) (- depthSum), чтобы получить ответ .