LeetCode--Binary Tree Maximum Path Sum

递归，dfs

这里返回值是一个pair<int,int>，first表示两个子树的不经过当前root的最大pathsum；second表示两个子树的，以root->left和root->right为路径起始节点的路径的最大值

 1 /**
 2  * Definition for binary tree
 3  * struct TreeNode {
 4  *     int val;
 5  *     TreeNode *left;
 6  *     TreeNode *right;
 7  *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 8  * };
 9  */
10 class Solution {
11 public:
12     int maxPathSum(TreeNode *root) {
13         pair<int,int> res = dfs(root);
14         return res.first;
15     }
16     pair<int,int> dfs(TreeNode *root)
17     {
18         if(root == NULL)
19         {
20             return make_pair(0,0);
21         }
22         pair<int,int> left = dfs(root->left);
23         pair<int,int> right = dfs(root->right);
24         int leftCrossMax = left.first;
25         int rightCrossMax = right.first;
26         
27         int leftMax = left.second > 0?left.second:0;
28         int rightMax = right.second > 0?right.second:0;
29         
30         int maxNoCross = INT_MIN;
31         if(root->left != NULL)
32         {
33             maxNoCross = max(maxNoCross,leftCrossMax);
34         }
35         if(root->right != NULL)
36         {
37             maxNoCross = max(maxNoCross,rightCrossMax);
38         }
39         int maxCross = leftMax+rightMax+root->val;
40         int maxSum = max(maxCross,maxNoCross);
41         
42         int child = max(leftMax,rightMax);
43         int maxChild = child > 0?child+root->val:root->val;
44         return make_pair(maxSum,maxChild);
45     }
46 };