EEPW论坛

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

Return6.

思路：

左子树延伸下去的路径

右子树眼神下去的路径

通过根节点的路径

注意返回这和最大值的关系；

1. class Solution  

2. {  

3.     int help(TreeNode* node, int& maxVal)  

4.     {  

5.         if (!node)  

6.         {  

7.             return 0;  

8.         }  

9.   

10.         int v1 = help(node->left, maxVal);  

11.         int v2 = help(node->right, maxVal);  

12.         int v = max(max(v1 + node->val, v2 + node->val), max(v1 + v2 + node->val, node->val));  

13.   

14.         maxVal = v>maxVal ? v : maxVal;  

15.   

16.         return max(max(v1 + node->val, v2 + node->val), node->val);//返回链接父节点时的最大值  

17.     }  

18.   

19.     int maxPathSum(TreeNode* root)  

20.     {  

21.         int maxVal = INI_MIN;  

22.         help(root, maxVal);  

23.   

24.         return maxVal;  

25.     }  

26. };