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.

----------------------- thinking -------------------------------

be careful about the question, the path may start and end at any node in the tree!! So in the codes, if the return of left and right is smaller than 0, we should reset them to 0, which means that that node should not be considered in the path.

---------------------- codes ----------------------------------

/**

 * 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) {

        if (root == NULL) return 0;

        int max = root->val;

        maxHelper(root, max);

        return max;

    }

    int maxHelper(TreeNode *node, int &max) {

        if (node == NULL) return 0;

        int path_max = 0;

        if (node->left == NULL && node->right == NULL) {

            if (node->val > max) {

                max = node->val;

            }

            return node->val;

        }

        int left = maxHelper(node->left, max);

        int right = maxHelper(node->right, max);

        //bug here, left and right should be reset to 0 if they are smaller than 0

        //the path may start and end at any node in the tree!

        left = left > 0? left:0;

        right = right > 0? right:0;

        if (node->val + left + right > max) {

            max = node->val + left + right;

        }

        return left > right ? left + node->val: right + node->val;

        

    }

};