leetcode第174场周赛第三题

Created 02/02/2020 at 04:18PM

题目概述

给你一棵二叉树，它的根为root。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 由于答案可能会很大，请你将结果对10^9 + 7取模后再返回。

代码

class Solution {
private:
    const int P = 1000000007;
    typedef long long ll;

    int get(TreeNode* root)
    {
        if (root == nullptr)return 0;
        return root->val + get(root->left) + get(root->right);
    }

    int work(TreeNode* root, int s, ll &ans)
    {
        if (root == nullptr) return 0;

        //注意理解这一句，后序遍历，有点类似于动态规划，只是没有存值
        int t = root->val + work(root->left, s, ans) + work(root->right, s, ans);

        ans = max(ans, (ll)t * (s - t));
        return t;
    }

public:
    int maxProduct(TreeNode* root) {
        int s = get(root);
        ll ans = 0;
        work(root, s, ans);
        return ans % P;
    }
};