Binary Tree Maximum Path Sum

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.

This could be solved using DP. For each node, the max sum path for its parent could be from its left (1) or right subtree (2) through itself or only itself (3) to its parent node (_maxSubPathSum). For the global max sum, it could be the sum of a node's left subtree through the node itself to its right subtree(4), plus the above 3 cases.
Time Complexity: O(n)

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (!root) return 0;
        
        int m = root->val;
        int localMax = _max(root, m);
        return localMax > m ? localMax : m;
    }
    
    int _max(TreeNode *root, int &m) {
        if (!root) return 0;
        int leftMax = _max(root->left, m);
        int rightMax = _max(root->right, m);
        
        int maxSum = max(root->val, max(root->val + leftMax, root->val + rightMax));
        m = max(max(m, maxSum), root->val + leftMax + rightMax);
        
        return maxSum; 
            
    }
};