JZX轻语：简
LeetCode 1339 - 分裂二叉树的最大乘积
发表于2024年07月31日
分析可知，切分后的两个子树的和越接近，乘积就越大。此外，其中一棵子树就是原树中以某个节点为根的子树，另外一棵则是以原树的根节点为根的、剩余节点构成的树。因此，只需要求出所有子树的和，然后找到和最接近总和一半的子树即可。
官解使用的是二次遍历的方法，首先第一次用于求和，然后第二次再找到最大的乘积。这里使用后序遍历的方法，一次遍历得到所有子树的和，然后再找到最接近总和一半的子树即可。
class Solution:
MOD = 10 ** 9 + 7
def maxProduct(self, root: Optional[TreeNode]) -> int:
tree_sums = [] # 保存所有子树的和
def inorder(node: Optional[TreeNode]):
if node is None:
return 0
tree_sum = inorder(node.left) + inorder(node.right) + node.val
tree_sums.append(tree_sum)
return tree_sum
inorder(root)
all_sum = tree_sums[-1] # 总和在最后一个元素(因为是后序遍历)
half = all_sum // 2 # 总和的一半
target = all_sum
for root_val in tree_sums:
if abs(target - half) > abs(root_val - half): # 找到一个和更接近总和一半的子树
target = root_val
return (target * (all_sum - target)) % self.MODC++的做法：
class Solution {
public:
using ll = long long;
vector<int> tree_sum_list;
ll inorder(TreeNode* node) {
if (node == nullptr) return 0;
ll sum = node->val + inorder(node->left) + inorder(node->right);
tree_sum_list.push_back(sum);
return sum;
}
int maxProduct(TreeNode* root) {
auto all_sum = inorder(root);
auto cand = all_sum;
auto half = all_sum / 2;
for (auto &tree_sum : tree_sum_list) {
if (abs(tree_sum - half) < abs(cand - half)) cand = tree_sum;
}
return cand * (all_sum - cand) % 1000000007;
}
};