найти максимальную сумму пути., Которую мы можем начинать и заканчивать в любом узле в двоичном дереве.

Question

вот проблема связи https://leetcode.com/problems/binary-tree-maximum-path-sum/, и мое решение - я могу преобразовать из дерева в массив, поэтому я согласен использовать предзаказ tree walk, и я ссылаюсь на алгоритм kadane, чтобы найти максимальное значение в массиве, вот мой код, когда я запускаю программу, результат всегда равен нулю, но, по моему мнению, это должно быть правильно, я не могу понять, почему это не работает, и, кстати, проблема подсказка использует dfs, я не знаком с dfs, может кто-нибудь подумать об этой проблеме с помощью метода dfs и рассказать мне, как хорошо изучать dfs, какие-либо документы или заметки , видео в порядке, спасибо заранее!

int maxPathSum(TreeNode *root) { 
    vector<int>res; 
    int max; 
    if (root){ 
     res.push_back(root->val); 
     maxPathSum(root->left); 
     maxPathSum(root->right); 
    } 
    else{ 
     return 0; 
    } 
    max = maxpathsum1(res); 
    return max; 
} 
int maxpathsum1(vector<int>&res){ 
    int cur,max; 
    int len = res.size(); 
    cur = 0; 
    max = 0; 
    for (int i=0;i<len-1;i++){ 
     cur = cur+res[i]; 
     if (cur<0){ 
      cur = 0; 
     } 
     if (max<cur){ 
      max = cur; 
     } 
    } 
    return max; 
} 

Answer 1

ДФС алгоритм для перемещения по всем узлам в дереве (в более общем случае в графе), так что это действительно может подходит к вашей проблеме. Вы можете просто запустить алгоритм dfs, суммируя максимальный путь каждый раз между левым поддеревом и правым + самим корневым узлом. Вы можете найти гораздо больше на dfs в книге Coreman's "Introduction to Algorithms".

Что касается вашего (очень похожего) решения, вы не используете возвращаемое значение рекурсии в функции «maxPathSum». Вы должны принять эти значения, возвращенные после вызова рекурсии на «root-> left» и «root-> right», проверить их положительность и суммировать их в некоторую переменную «max2» и использовать ее.