【LeetCode】Binary Tree Maximum Path Sum

递归。每到一个节点计算其左右子树的最大路径和。
如果左或者右子树的最大路径和比已经找到的最大路径和大则更新。
如果以这个节点为根节点能得到的最大路径和比已经找到的最大路径和大则更新。
每次递归返回此节点值与左右子树最大路径和中较大者的和。

/**
 * Definition for binary tree
 * struct TreeNode {
 * int val;
 * TreeNode *left;
 * TreeNode *right;
 * TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxSum(TreeNode *root) {
        int left=0,right=0;
        if(root->left)
        {
            left=maxSum(root->left);
            if(left>re) re=left;
        }
        if(root->right)
        {
            right=maxSum(root->right);
            if(right>re) re=right;
        }
        int sum=root->val+(left>0?left:0)+(right>0?right:0);
        if(sum>re) re=sum;
        int child=(left>right)?left:right;
        return root->val+(child>0?child:0);
    }
    int maxPathSum(TreeNode *root) {
        if(NULL==root) return 0;
        re=0x80000000;
        maxSum(root);
        return re;
    }
private:
    int re;
};