Leetcode-124. 二叉树中的最大路径和

发表于 分类于 阅读次数：

https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/

解法1：递归

思路：

以abc二叉树为例a是递归中的根节点，b，c是左右子节点（代表递归后的最优解）

1
2
3
  a
 / \
b   c

则最大路径有这么三种情况：

1.b+a+c

2.b+a+a的父节点

3.c+a+a的父节点

注意：其中节点有可能是负值，最大和要想办法舍弃负值（max（0，x））

所以我们可以递归，同时记录全局最大和，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    int res=INT_MIN;
public:
    int maxPathSum(TreeNode* root) {
        maxp(root);
        return res;
    }
    int maxp(TreeNode *root)
    {
        if(root==NULL)
            return 0;
        int l=maxp(root->left);
        int r=maxp(root->right);
        int les=max(l,0)+max(r,0)+root->val;
        int ret=root->val+max(0,max(l,r));
        res=max(res,max(les,ret));
        //注意返回值，我们要返回当前节点和左子树的最大值或当前节点和右子树的最大值
        return ret;
    }
};