本题是第174场周赛的 Q3,LC竞赛分为1675.
方法一. 递归(超时)
单纯使用递归对每一个节点进行遍历,代码如下:
class Solution {
long long ans = -1;
public:
int maxProduct(TreeNode* root) {
long long total_sum = sum(root);
dfs(root,total_sum);
return ans%(int)(1e9+7);
}
long long sum(TreeNode* root){
if(root == NULL) return 0;
return root->val+sum(root->left)+sum(root->right);
}
void dfs(TreeNode* root,long long total_sum){
if(!root) return;
long long a1 = sum(root);
long long a2 = total_sum-a1;
ans = max(a1*a2,ans);
dfs(root->left,total_sum);
dfs(root->right,total_sum);
}
};
方法二. 后序遍历+记忆化搜索(时间超过 11.89% cpp用户)
后序遍历+记忆化搜索可以让父节点直接用到子节点的结果,从而减少递归调用。代码如下:
class Solution {
long long ans = -1;
public:
int maxProduct(TreeNode* root) {
long long total_sum = sum(root);
map<TreeNode*,long long> record;
dfs(root,total_sum,record);
return ans%(int)(1e9+7);
}
long long sum(TreeNode* root){
if(root == NULL) return 0;
return root->val+sum(root->left)+sum(root->right);
}
void dfs(TreeNode* root,long long total_sum,map<TreeNode*,long long>& record ){
if(!root) return;
dfs(root->left,total_sum,record);
dfs(root->right,total_sum,record);
long long a1,a2;
if(record.count(root->left)==1){
a1 = record[root->left];
}
else
a1 = sum(root->left);
if(record.count(root->right)==1){
a2 = record[root->right];
}
else
a2 = sum(root->right);
long long sum_tmp = a1 + a2 + root->val;
record[root] = sum_tmp;
ans = max(ans,sum_tmp*(total_sum-sum_tmp));
return;
}
};
标签:1339,sum,long,力扣,record,二叉树,return,total,root
From: https://blog.csdn.net/Bright_Brilliant/article/details/139645226