题解 | #二叉树中的最大路径和#

思路：最大路径和的产生：左子树的单路径、右子树的单路径、左右子树的单路径和根节点值这三者之一。因此，先用两个变量存储左右子树的单路径（单路径就是只有从下到上的一条路径，没有左右）的最大和，分别取最大值即可。需要注意的是，取某条单路径的最大和的时候，如果某子树单路径之和加上根节点的值比根节点小，那么该子树的单路径之和直接舍弃。

class Solution {
public:
    int max_value = -32768;
    int maxPathSum(TreeNode* root) {
        return max(max_value,func(root));
    }
    int func(TreeNode* root){
        if(!root)return 0;
        int left = func(root->left);
        int right = func(root->right);
        max_value = max(left + root->val + right, max_value);
        return max(left + root->val, max(right + root->val, root->val));
    }
};