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

解题思路： 主要抓住某一个结点，采取后续遍历的思想。 在返回值时，一个结点有三种情况：

1. leftchild + rightchild + root-> val;
2. leftchild + root->val;
3. rightchild + root->val; 那么result的最大值就可能为上述三者中的最大值，依次执行后续遍历即可得出最优解。

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

class Solution {
public:
    /**
     * 
     * @param root TreeNode类 
     * @return int整型
     */
    int result = -1001;
    int dfs(TreeNode* root){
        if(root == NULL)
            return 0;
        int left = dfs(root->left);
        int right = dfs(root->right);
        int ll = left + root->val;
        int rr = right + root->val;
        result = max(result,left + right + root->val);
        result = max(result,max(ll,rr));
        result = max(root->val,result);
        return (ll > rr ? (ll > root->val ? ll : root->val) : (rr > root->val ? rr : root->val)); 
    }
    int maxPathSum(TreeNode* root) {
        if(root == NULL)
            return 0;
        dfs(root);
        return result;
    }
};