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.

 

用递归确定每一个节点作为root时，从root出发的最长的路径

在每一次递归中计算maxPath

 

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 maxSum=INT_MIN;13     int maxPathSum(TreeNode *root) {14        15         DFS(root);16         return maxSum;17     }18    19     int DFS(TreeNode *root)20     {21         if(root==NULL)22         {23             return 0;24         }25        26         int left=DFS(root->left);27         int right=DFS(root->right);28        29         int sum=root->val;30         if(left>0) sum+=left;31         if(right>0) sum+=right;32         if(maxSum
      
       0||right>0)?root->val+max(left,right):root->val;35     }36 };