二叉树的最大路径和ACM模式

二叉树的最大路径和ACM模式是一个经典的算法问题。在这个模式中，我们需要找到二叉树中两个节点之间的路径，使得路径上节点值的和最大。为了解决这个问题，我们可以使用递归的方法。

首先，我们定义一个辅助函数helper来计算从当前节点开始的最大路径和。在这个函数中，我们首先检查当前节点是否为空，如果是空节点，则返回0。然后，我们递归地计算左子树和右子树的最大路径和，分别存储在变量l和r中。接下来，我们计算过当前节点的最大路径和curSum，它可以是当前节点的值与左子树路径和、右子树路径和的和中的最大值。然后，我们计算如果将当前节点作为根节点时的最大路径和curMax，它可以是curSum与左子树路径和、右子树路径和的和中的最大值。最后，我们更新全局最大路径和m为m和curMax中的较大值，并返回过当前节点的最大路径和curSum。

在主函数maxPathSum中，我们首先检查根节点是否为空，如果是空节点，则返回0。然后，我们定义一个变量m来存储全局最大路径和的初始值INT_MIN。接下来，我们调用辅助函数helper来计算最大路径和，并将m传入函数，以便在函数中更新最大值m。最后，我们返回最大路径和m。

代码实现如下：

int maxPathSum(TreeNode* root) {
    if(!root)
        return 0;
    int m=INT_MIN;
    helper(root,m);
    return m;
}

int helper(TreeNode* root,int &m) {
    if(!root)
        return 0;
    int l=helper(root->left,m);
    int r=helper(root->right,m);
    int curSum=max(root->val,max(l+root->val,r+root->val));
    int curMax=max(curSum,l+r+root->val);
    m=max(m,curMax);
    return curSum;
}