题目链接：Binary Tree Maximum Path Sum

Given a binary tree, find the maximum path sum.

The path may start and end at any node in the tree.

For example:

Given the below binary tree,

       1 
      / \ 
     2   3

Return 6.

这道题的要求是找到二叉树中最大的路径和，其中路径可以从任意节点开始和结束。

递归，采用自底向上的思路，依次求出以每个点为根节点的最大路径和，并找出最大值。假设当前节点为p，则以p为根节点的最大路径和等于p->val加上p的左右节点分别到叶子节点的最大路径和，即为p->val + findMax(p->left) + findMax(p->right)，其中findMax(p)函数计算节点p到叶子节点的最大路径和。而当前p节点到叶子节点的最大路径和就等于p->val加上findMax(p->left)和findMax(p->right)中的较大值。

时间复杂度：O(n)

空间复杂度：O(1)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution
{
    int res = INT_MIN;
public:
    int maxPathSum(TreeNode *root)
    {
        findMax(root);
        return res;
    }
private:
    // 返回节点p到叶子节点的最大路径和
    int findMax(TreeNode *p)
    {
        if(p == NULL)
            return 0;
        
        int left = findMax(p -> left);
        int right = findMax(p -> right);
        res = max(p -> val + left + right, res);
        int temp = p -> val + max(left, right);
        return temp > 0 ? temp : 0;
    }
};