咨询：求解二叉树最大子树和的代码错误原因

• 返回类型不匹配：subTree函数声明返回pair<long long, long long>，但空节点分支中创建并返回的是pair<int, int>。虽然C++允许隐式转换，但这是不规范写法，可能引发类型相关潜在问题，应统一使用long long类型的pair。

• 整数溢出风险：将left.first、right.first（均为long long类型）强制转换为int类型的leftsum、rightsum，后续计算的totalsum也用int存储。当树的节点和超过int取值范围时，会发生溢出导致计算结果错误，所有涉及求和的变量都应使用long long类型。

• 最大子树和逻辑遗漏：当前计算maxi时，仅比较了当前子树总和、左子树总和、右子树总和，完全忽略了左子树内部已找到的最大子树和（left.second）与右子树内部已找到的最大子树和（right.second）。例如左子树中存在子树和大于当前整棵子树总和时，当前逻辑会漏掉这个正确最大值。

• 空节点初始值错误：当树中所有节点数值均为负数时，空节点返回的(0, 0)会干扰结果。比如仅存在一个值为-5的节点，当前代码会返回0，但正确的最大子树和应为-5。空节点的初始最大子树和应设为负无穷（如LLONG_MIN），总和可设为0。

修正后的示例代码 #

#include <climits>
#include <algorithm>
using namespace std;

pair<long long, long long> subTree(BinaryTreeNode<int> *root){
    if(root == NULL ){
        // 总和为0，最大子树和设为负无穷，避免干扰负数节点的计算
        pair<long long, long long> p = make_pair(0LL, LLONG_MIN);
        return p;
    }

    pair<long long, long long> left = subTree(root->left);
    pair<long long, long long> right = subTree(root->right);

    long long leftsum = left.first;
    long long rightsum = right.first;
    long long totalsum = leftsum + rightsum + root->data;
    
    // 同时比较当前子树总和、左子树内部最大值、右子树内部最大值
    long long maxi = max({totalsum, left.second, right.second});
    
    pair<long long, long long> ans = make_pair(totalsum, maxi);
    return ans;
}

long long maxSubtreeSum(BinaryTreeNode<int> *root){
    pair<long long, long long> p = subTree(root);
    return p.second;
}

内容的提问来源于stack exchange，提问作者Tanuj