帮忙看看我的code能否处理一个孩子的情况?
测试树:
8
/ \
/ \
/ \
/ \
/ \
0 14
/ \ / \
/ \ / \
/ \ 11 5
17 24 \ \
\ / \ 12 45
34 / \
19 28
答案: 28 和 45
最大和124
typedef pair Item;
Item MaxpathSum(Tree *node, int &CurMaxSum, int SumToNow, Tree *&ln, Tree *&rn)
{
if (node->left && !node->right) {
Item leftPathMax = MaxpathSum(node->left, CurMaxSum, SumToNow+node->element, ln, rn);
return Item(node->element+node->left->element, leftPathMax.second);
} else if (node->right && !node->left) {
Item rightPathMax = MaxpathSum(node->right, CurMaxSum, SumToNow+node->element, ln, rn);
return Item(node->element+node->right->element, rightPathMax.second);
} else if (!node->left && !node->right) {
return Item(node->element, node);
}
Item leftPathMax = MaxpathSum(node->left, CurMaxSum, SumToNow+node->element, ln, rn);
Item rightPathMax = MaxpathSum(node->right, CurMaxSum, SumToNow+node->element, ln, rn);
int MaxSum = leftPathMax.first + node->element + rightPathMax.first + SumToNow;
cout << MaxSum << endl;
if (MaxSum > CurMaxSum) {
CurMaxSum = MaxSum;
ln = leftPathMax.second;
rn = rightPathMax.second;
}
return leftPathMax.first > rightPathMax.first ?
Item(leftPathMax.first+node->element, leftPathMax.second):
Item(rightPathMax.first+node->element, rightPathMax.second);
}
void Find_Max_Pair(Tree *root)
{
int MaxSum = INT_MIN;
int CurMaxSum = INT_MIN;
int SumToNow = 0;
Tree *ln;
Tree *rn;
Item test = MaxpathSum2(root, MaxSum, SumToNow, ln, rn);
return;
}