天池 在线编程 最大子树（自底向上）

示例
样例 1:
输入:
{1,-5,2,0,3,-4,-5}
输出:3
说明
这棵树如下所示：
     1
   /   \
 -5     2
 / \   /  \
0   3 -4  -5
以3为根的子树（只有3一个节点）的和是最大的，所以返回3。

样例 2:
输入:
{1}
输出:1
说明:
这棵树如下所示：
   1
这棵树只有整体这一个子树，所以返回1.

/**
 * Definition of TreeNode:
 * class TreeNode {
 * public:
 *     int val;
 *     TreeNode *left, *right;
 *     TreeNode(int val) {
 *         this->val = val;
 *         this->left = this->right = NULL;
 *     }
 * }
 */

class Solution {
    int ans = INT_MIN;
    TreeNode *res = NULL;
public:
    /**
     * @param root: the root of binary tree
     * @return: the maximum weight node
     */
    TreeNode * findSubtree(TreeNode * root) {
        // write your code here
        find(root);
        return res;
    }
    int find(TreeNode* root)
    {
        if(!root) return INT_MIN;
        int l = find(root->left); // 左子树的总和
        l = (l==INT_MIN ? 0 : l);
        int r = find(root->right);// 右子树的总和
        r = (r==INT_MIN ? 0 : r);
        int s = l+r+root->val; //当前子树的总和
        if(s > ans)// 记录最大的
        {
            ans = s;
            res = root;
        }
        return s;
    }
};