Binary Tree Maximum Path Sum II

题目：

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.

接口：

class Solution {
public:
    /**
     * @param root the root of binary tree.
     * @return an integer
     */
    int maxPathSum2(TreeNode *root) {
        // Write your code here

    }
};

分析：

其实问题想起来比较难，有很多种情况，但是在实际处理的时候，如果一个孩子结点返回的值<0，那么我们根本不会考虑他。所以，这道题的解法是在返回值中于0作比较。当然，既然题目要求经过root，所以root得值总是要加上去的。

定义结点：

struct TreeNode{
public:
  int val;
  TreeNode* left;
  TreeNode* right;
  TreeNode(int x) : val(x), left(NULL), 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 maxSum = root->val;
        int left = maxPathSum2(root->left);
        int right = maxPathSum2(root->right);

        return max(0, max(left, right) ) + root->val;
    }
};