[leetcode] 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.

Here I consider a recursive solution. We update the 'val' field of each node with the path sum ending at that node (starting from any one of its descendants). We keep a 'max_sum' variable to save the current maximum path sum. We update this variable using paths going through the node, paths ending at this node, and the single-node path. We traverse the binary tree once, so the time complexity is 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:

    void max_path_helper(TreeNode *root, int &max_sum)
    {
        if (!root) return;
        else
        {
            max_path_helper(root->left, max_sum);
            max_path_helper(root->right, max_sum);
           
            int left_sum = 0, right_sum = 0;
            if (root->left)
                left_sum = (root->left)->val;
            if (root->right)
                right_sum = (root->right)->val;
           
            // update max sum
            int sum = left_sum + right_sum + root->val;
            int sum_left = left_sum + root->val;
            int sum_right = right_sum + root->val;
           
            if (max_sum < sum)
                max_sum = sum;
               
            if (max_sum < sum_left)
                max_sum = sum_left;
           
            if (max_sum < sum_right)
                max_sum = sum_right;
               
            if (max_sum < root->val)
                max_sum = root->val;
           
            // compare with child sums and single value at this node
            int tmp = 0;
            if (left_sum > right_sum)
                tmp = root->val + left_sum;
            else
                tmp = root->val + right_sum;
               
            // update value
            if (tmp > root->val)
                root->val = tmp;
        }
       
    }
   
    int maxPathSum(TreeNode *root) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
       
        // current max sum
        int max_sum = -999;
       
        // for each node, compute the max sum of the path starting at this node
        // update max_sum using the max_sum's of its two subtrees
        if (!root)
            return 0;
           
        max_path_helper(root, max_sum);
       
        // finally compare the current max sum with the path sum ending at root
        if (max_sum < root->val)
            max_sum = root->val;
           
        return max_sum;
    }
};