二叉树的递归求最大和问题

**112. Path Sum **
Given a binary tree and a sum, determine if the tree has a root-to-leaf path such that adding up all the values along the path equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \      \
        7    2      1

return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
代码如下：

class Solution {
public:
    bool hasPathSum(TreeNode* root, int sum) {
        if(root==NULL)
          return false;
        if(root->val==sum&&root->left==NULL&&root->right==NULL) //正好是这个节点，且为最底层的节点（左右子树为空）
          return true;
        else
          return hasPathSum(root->left,sum - root->val)||hasPathSum(root->right,sum - root->val);
    }
};

**113. Path Sum II **
Given a binary tree and a sum, find all root-to-leaf paths where each path's sum equals the given sum.
For example:
Given the below binary tree and sum = 22,

              5
             / \
            4   8
           /   / \
          11  13  4
         /  \    / \
        7    2  5   1

return

[
   [5,4,11,2],
   [5,8,4,5]
]

代码如下：

class Solution {
public:
    
    vector<vector<int>> pathSum(TreeNode* root, int sum) {
        vector<vector<int>> rec;
        vector<int> temp;
        if(root==NULL)
          return rec;
        DFS(root,sum,rec,temp);
        return rec;
    }
    void DFS(TreeNode* root,int sum,vector<vector<int>> &rec,vector<int> &temp)
    {
        if(root==NULL)
          return;
        temp.push_back(root->val);//注意：这里压入
        if(root->val==sum&&root->left==NULL&&root->right==NULL)
            rec.push_back(temp);
            
        if(root->left)
          DFS(root->left,sum - root->val,rec,temp);
        if(root->right)
          DFS(root->right,sum - root->val,rec,temp);
        temp.pop_back();//注意：这里弹出
    }
};

**129. Sum Root to Leaf Numbers **
Given a binary tree containing digits from 0-9 only, each root-to-leaf path could represent a number.

An example is the root-to-leaf path 1->2->3 which represents the number 123.
Find the total sum of all root-to-leaf numbers.
For example,

    1
   / \
  2   3

The root-to-leaf path 1->2 represents the number 12.
The root-to-leaf path 1->3 represents the number 13.
Return the sum = 12 + 13 = 25.
代码如下：

class Solution {
public:
    int sumNumbers(TreeNode* root) {
        return dfs(root,0);
    }
    int dfs(TreeNode* root,int sum)
    {
        if(root==NULL)
          return 0;
        if(root->left==NULL&&root->right==NULL)
          return 10*sum + root->val;
        else
          return dfs(root->left,10*sum + root->val) + dfs(root->right,10*sum + root->val);
    }
};

**124. Binary Tree Maximum Path Sum **
Given a binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

For example:
Given the below binary tree,

       1
      / \
     2   3

Return 6.
代码如下：

class Solution {
public:
    int sum = INT_MIN;
    int maxPathSum(TreeNode* root) {
        if(root==NULL)
          return 0;
        mSum(root);
        return sum;
    }
    int mSum(TreeNode* root)
    {
        if(root==NULL)
          return 0;
        int left = mSum(root->left);
        int right = mSum(root->right);
        int current = max(max(left+root->val,right+root->val),root->val);
        int result = max(current,left+right+root->val);
        sum = max(sum,result);
        return current;
    }
};