Given a binary tree, find the maximum path sum from root.

The path may end at any node in the tree and contain at least one node in it.

Have you met this question in a real interview?

Yes

Example

Given the below binary tree:

  1
 / \
2   3

return4. (1->3)

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */
class Solution {
public:
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    int maxPathSum2(TreeNode *root) {
        // Write your code here
        if (root == NULL) {
            return 0;
        }
        int maxLeft = maxPathSum2(root->left);
        int maxRight = maxPathSum2(root->right);
        int maxSofar = max(maxLeft, maxRight);
        maxSofar = max(maxSofar, 0);
        return root->val + maxSofar;
    }
};