124. Binary Tree Maximum Path Sum

The idea is very similar to maximum subarray sum problem where a dp array is used to store the local maximal subarray sum at position i, and a global maximal subarray sum variable is updated as the final result. For this problem, we also need to keep the local maximal path and the global maximal path. The following code is what I did in first place.

However, this piece of code is wrong. The helper function returns not the maximal sum on a path (i.e. left->root, or right->root) but the maximal sum for the whole subtree.

1:  /**  
2:   * Definition for a binary tree node.  
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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);
21:      int postMax = helper(root->right);
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      if (root->val > val) val = root->val;  
24:      maxSum = max(val, maxSum);  
25:      return val;  
26:    }  
27:  };  

So I modified the code and eventually got the right solution.

1:  /**  
2:   * Definition for a binary tree node.  
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:  private:  
12:    int maxSum = INT_MIN;  
13:  public:  
14:    int maxPathSum(TreeNode* root) {  
15:      helper(root);  
16:      return maxSum;  
17:    }  
18:    int helper(TreeNode *root) {  
19:      if (root == NULL) return 0;  
20:      int prevMax = helper(root->left);  
21:      int postMax = helper(root->right);  
22:      int val = max(root->val+prevMax, max(root->val+postMax, max(root->val+prevMax+postMax, root->val)));  
23:      maxSum = max(val, maxSum);  
24:      return max(root->val+prevMax, max(root->val+postMax, root->val));  
25:    }  
26:  };