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,
Given the below binary tree,
1 / \ 2 3
Return
Analysis:
6
.Note: the maximum path doesn't have to include the root. So, if we do DFS, we need to record the maximum path sum of a sub tree. For root->left, the DFS function should return the maximum path sum that ends at root->left, in order to connect to root. root->right should be the same.
class Solution { public: int maxPathSum(int & maxSum, TreeNode* root) { if(!root) return 0; int tmp = root->val; int left = maxPathSum(maxSum, root->left); if(left>0) tmp+=left; int right = maxPathSum(maxSum, root->right); if(right>0) tmp+=right; //Note: maxSum has already been compared with left and right // in recursive calls maxSum = max(tmp, maxSum); return max(root->val, max(left, right) + root->val); } int maxPathSum(TreeNode* root) { if(!root) return 0; int maxSum = INT_MIN; int res = maxPathSum(maxSum, root); return max(res, maxSum); } };