学步园

题目要求：

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.

代码：

class Solution {
public:
  int maxPathSum(TreeNode *root) {
    if(root == NULL)
      return 0;
    int sum = numeric_limits<int>::min();
    DFS(root, sum);
    return sum;
  }
  
  int DFS(TreeNode* root, int &max_sum)//返回以root为根节点的最大和，要么是root本身最大，或者是 root + root 左子树的最大和，或者root+root右子树中最大和
  {
    if(root == NULL)
      return 0;
    int left = DFS(root->left, max_sum);
    int right = DFS(root->right, max_sum);
    int tmp_sum = root->val;//计算出以当前节点为根节点时的路径最大的和
    if(left > 0)//如果左子树最大和大于零，加上左子树会使和更大
      tmp_sum += left;
    if(right > 0)
      tmp_sum += right;
    max_sum = max(tmp_sum, max_sum);
    return max(root->val, max(root->val + left, root->val + right));
  }
  
};