本文主要是介绍力扣刷题记录： 1339. 分裂二叉树的最大乘积，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
本题是第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];}elsea1 = sum(root->left);if(record.count(root->right)==1){a2 = record[root->right];}elsea2 = 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. 分裂二叉树的最大乘积的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
