Правильна ли моя логика? Это дает ошибку сегментации
Я хочу найти максимальную сумму от корня до листа в двоичном дереве.
Изначально я делаю: Answer= sum_to_leaf(root,0);
Я знаю другой способ изучить весь путь и обновить глобальный максимум на сумму. Я просто хочу сделать это таким образом.
int sum_to_leaf(struct node* root, int sum)
{
if(root == NULL)
return sum;
else if(root->left == NULL && root->right == NULL)
{
sum = sum + root->data;
return sum;
}
else
{
sum = sum + root->data;
if(sum_to_leaf(root->left, sum) > sum_to_leaf(root->right, sum))
{
sum = sum + sum_to_leaf(root->left, sum);
}
else
{
sum = sum + sum_to_leaf(root->right, sum);
}
return sum;
}
}
Решение
Ммм, вы уверены, что сегфо происходит из этого кода? Вы отладили это?
Я лучше попробую это:
int sum_to_leaf(struct node* root,int sum) {
if(root==NULL) {
return sum;
} else {
sum=sum+root->data;
int left_sum = sum_to_leaf(root->left, sum);
int right_sum = sum_to_leaf(root->right, sum);
return std::max(left_sum, right_sum); // need to #include <algorithm>
}
}
Другие решения
Вы, должно быть, неправильно строите свое дерево. Где-то вы получаете доступ к неинициализированным node хоть root-> и получить ошибку сегмента.
Я думаю, что лучший способ реализовать ваш алгоритм:
int getSum(struct node* nd)
{
if(nd==NULL)
return 0;
int sum_r = getSum(nd->right);
int sum_l = getSum(nd->left);
return nd->data + std::max(sum_r, sum_l);
}
detector