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.

思路：

递归调用函数。用函数comput计算从子树到根节点传递到根节点的父节点的值，然后用一个result记录在递归过程中求得的最大值。

代码：

 1     int max(int a, int b){
 2         if(a > b)
 3             return a;
 4         return b;
 5     }
 6     int comput(TreeNode *root, int &result){
 7         if(root == NULL)
 8             return 0;
 9         int left = comput(root->left, result);
10         int right = comput(root->right, result);
11         int arch = left + right + root->val;
12         int valToParent = max(root->val, root->val+max(left, right));
13         result = max(result, max(arch, valToParent));
14         return valToParent;
15     }
16     int maxPathSum(TreeNode *root) {
17         // IMPORTANT: Please reset any member data you declared, as
18         // the same Solution instance will be reused for each test case.
19         int result = INT_MIN;
20         comput(root, result);
21         return result;
22     }