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.

接口：

class Solution {
public:
    /**
     * @param root: The root of binary tree.
     * @return: An integer
     */
    int maxPathSum(TreeNode *root) {

    }
};

分析：

根据题目要求维护一个全局的max，每次dfs的时候更新这个max。但是dfs的返回值并不是max，而是left或者right中的一支。如果left和right最大值比0还小，那么返回0。dfs讨论的是到目前一个结点为止，左边大还是右边大还是都比0小。这个dfs的返回值会影响其上一层，但未必会影响全局max。

定义结点：

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 ans = INT_MIN; 

    int dfs(TreeNode* root) {
        if (root == NULL) {
            return 0;
        }

        int sum = root->val;
        int maxL = dfs(root->left);
        int maxR = dfs(root->right);

        if (maxL > 0) {
            sum += maxL;
        }
        if (maxR > 0) {
            sum += maxR;
        }

        ans = max(ans, sum);
        return max(0, max(maxL, maxR) ) + root->val;
    }  

    int maxPathSum(TreeNode *root) {
        // write your code here
        if (root == NULL) {
            return 0;
        }
        dfs(root);
        return ans;
    }
};