链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/by-xun-ge-v-7r1v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 

题目

示例

思路

解题思路
对于树的相关问题递归基本上都可以解决
本题也不例外，分析题意，需要我们寻找二叉树的最大路径

对于任意一个节点，都存在四个路径

• 自己本身就是一个有效路径
• 左节点是一个有效路径
• 右节点是一个有效路径
• 自己本身+左节点+右节点是一个有效路径

每次递归我们只需要比较这四个路径那个值高就保存那个值

通过上述我们知道，在求任意一个节点路径时，都要先知道左节点路径和右节点路径值才能比较，所以应该从下往上遍历数节点，先计算下层路径最大值，为上层路径准备，同时动态更新每一天节点，避免反复计算，实现记忆化搜索

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

#define MAX(a , b) ((a) > (b) ? (a) : (b))
int maxPathSum(struct TreeNode* root){
    int max = INT_MIN;//保存最大值
    int val = root->val;//临时保存当前节点，路径1
    if(root->left)//判断是否存在右节点
    {
        int left = maxPathSum(root->left);//路径2
        max = MAX(max , left);//每次保存最大路径
        val = MAX(val , root->val + root->left->val);//临时保存，动态更新当前节点
    }
    if(root->right)
    {
        int right = maxPathSum(root->right);//路径3
        max = MAX(max , right);//每次保存最大路径
        val = MAX(val , root->val + root->right->val);
    }
    if(root->left && root->right)
    {
        max = MAX(max , root->val + root->left->val + root->right->val);//路径4
    }
    root->val = val;//更新当前节点
    max = MAX(max, root->val);
    return max;
}


作者：xun-ge-v
链接：https://leetcode.cn/problems/binary-tree-maximum-path-sum/solution/by-xun-ge-v-7r1v/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。