求二叉树中最大和的路径（递归法）c++

在C++中，我们可以使用递归的方法来解决求二叉树中最大和的问题。这个问题通常被称为“最大子数组和”问题在二叉树中，我们寻找的是从根节点到叶子节点的所有路径，其中数字相加的总和最大。

以下是一个基本的递归算法步骤：

1. 定义基本情况：如果当前节点为空，返回0，因为路径和为空；
2. 如果当前节点不空，计算以当前节点为结尾的左子树的最大和 `leftMax` 和右子树的最大和 `rightMax`；
3. 计算包含当前节点值的路径和，即当前节点值加上左子树的最大和 `leftMax` 或右子树的最大和 `rightMax` 中的最大者，取名为 `maxPathSum`；
4. 返回 `max(leftMax, rightMax) + nodeValue`，即左右子树的最大和加上当前节点值，作为当前节点参与的最大和路径。

以下是C++代码实现：

#include <climits>

struct TreeNode {
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};

int maxPathSum(TreeNode* root) {
    if (!root) return 0;
    int leftMax = maxPathSum(root->left);
    int rightMax = maxPathSum(root->right);
    int maxWithNode = std::max(leftMax, rightMax) + root->val;
    int withoutNode = std::max(leftMax, rightMax);
    return std::max(maxWithNode, withoutNode);
}