二叉树最大路径和C语言

二叉树的最大路径和是指在一棵给定的二叉树中找到从根节点到某个叶子节点的路径，使得路径上所有节点值的和最大。这个问题可以使用动态规划来解决。在C语言中，我们可以创建一个递归函数来遍历二叉树并计算每个节点路径的和。

以下是简单的步骤和伪代码：

1. 定义一个结构体表示二叉树节点：

typedef struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

2. 创建两个辅助函数：`maxPathSumHelper` 和 `maxPathSum`。`maxPathSumHelper` 用于计算单个节点的路径和，并返回当前节点加上左右子节点路径和的最大值；`maxPathSum` 则负责记录全局最大路径和。

int maxPathSumHelper(TreeNode* node, int currentMax) {
    if (node == NULL) return 0;

    // 计算左子树、右子树加上当前节点的路径和
    int left = maxPathSumHelper(node->left, 0);
    int right = maxPathSumHelper(node->right, 0);

    // 如果取左或取右都能增加路径和，选择较大的那一个
    int includeNode = node->val + (currentMax > 0 ? currentMax : left || right);
    int excludeNode = currentMax >= node->val ? currentMax : 0;

    // 返回包含当前节点和不包含当前节点的最大路径和
    return max(includeNode, excludeNode);
}

int maxPathSum(TreeNode* root) {
    return maxPathSumHelper(root, INT_MIN); // 初始化当前最大为负无穷大，保证不会溢出
}