求树的最大途径和

求树的最大路径和

Problem：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.

这里所说的路径和是指从任意结点开始到任意结点结束的结点值之和，而且要注意的是结点的值也可能为负数。

思路：用递归思想，并用一个全局变量保存最大路径和的值。分别求当前结点的左子树和右子树的最大路径和，返回通过当前结点的最大路径和。并将下列四个值最大值与当前最大路径和比较，保证最大路径和始终是最大值。

当前结点值

当前结点值+左子树的最大路径和

当前结点值+右子树最大路径和

当前结点值+左子树最大路径和+右子树最大路径和

注意：这里在每次求通过一个结点的最大路径和时，不断更新整个树的最大路径和。

class Solution {
public:
   int res;//保存最大路径和  
    int maxPathSum(TreeNode* root) {  
        res =  -10000;  
        maxPathSumRe(root);    
        return res;    
    }    
    
    int maxPathSumRe(TreeNode* node)    
    {    
        if (node == NULL) return 0;  
        int l = maxPathSumRe(node->left);  
        int r = maxPathSumRe(node->right);  
        int maxSub = (l > r) ? l : r;
        //sum用于保存通过当前结点的最大路径和
        int sum = (node->val > maxSub + node->val) ? node->val : node->val + maxSub;  
        res = res > sum ? res : sum;  
        res = node->val + l + r > res ? node->val + l + r : res;   
        return sum;   
    }    
};