leetcode

commit c478fb6dd1b3631fc5a137df94dc3abdf2628f0e
parent c401501510dde75975e5da2cda01fde04c2dbd71
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue,  6 Jan 2026 21:49:07 -0700

1339. maximum product of splitted binary tree

Diffstat:
A
max_product_split_bin_tree.c
 | 
44
++++++++++++++++++++++++++++++++++++++++++++
A
max_product_split_bin_tree.py
 | 
44
++++++++++++++++++++++++++++++++++++++++++++

2 files changed, 88 insertions(+), 0 deletions(-)
diff --git a/max_product_split_bin_tree.c b/max_product_split_bin_tree.c
@@ -0,0 +1,44 @@
+// 1339. Maximum Product of Splitted Binary Tree
+#include "leetcode.h"
+
+/*
+ * given the 'root' of a binary tree, split the binary tree into two subtrees by
+ * removing one edge such that the product of the sums of the subtrees is
+ * maximised. return the maximum product of the sums of the two subtrees. since
+ * the answer may be too large, return it modulo 10^9+7. note that you need to
+ * maximise the answer before taking the mod, and not after.
+ */
+
+static long long total, best;
+
+long long sum(struct TreeNode *node) {
+  if (!node)
+    return 0;
+  return node->val + sum(node->left) + sum(node->right);
+}
+
+long long dfs(struct TreeNode *node) {
+  if (!node)
+    return 0;
+  long long s = node->val + dfs(node->left) + dfs(node->right);
+  long long p = s * (total - s);
+  best = fmax(best, p);
+  return s;
+}
+
+int maxProduct(struct TreeNode *root) {
+  total = sum(root);
+  best = 0;
+  dfs(root);
+  return best % (long long)(1e9 + 7);
+}
+
+int main() {
+  int r1i[] = {1, 2, 3, 4, 5, 6}, r2i[] = {1, -1, 2, 3, 4, -1, -1, 5, 6};
+  struct TreeNode *r1 = treenode_build(r1i, ARRAY_SIZE(r1i));
+  struct TreeNode *r2 = treenode_build(r2i, ARRAY_SIZE(r2i));
+  printf("%d\n", maxProduct(r1)); // expect: 110
+  printf("%d\n", maxProduct(r2)); // expect: 90
+  treenode_free(r1);
+  treenode_free(r2);
+}
diff --git a/max_product_split_bin_tree.py b/max_product_split_bin_tree.py
@@ -0,0 +1,44 @@
+# 1339. Maximum Product of Splitted Binary Tree
+import leetcode
+
+"""
+given the 'root' of a binary tree, split the binary tree into two subtrees by
+removing one edge such that the product of the sums of the subtrees is
+maximised. return the maximum product of the sums of the two subtrees. since
+the answer may be too large, return it modulo 10^9+7. note that you need to
+maximise the answer before taking the mod, and not after.
+"""
+
+
+class Solution(object):
+    def total_sum(self, node):
+        if not node:
+            return 0
+        return node.val + self.total_sum(node.left) + self.total_sum(node.right)
+
+    def maxProduct(self, root):
+        """
+        :type root: Optional[TreeNode]
+        :rtype: int
+        """
+        self.best = 0
+
+        total = self.total_sum(root)
+
+        def dfs(node):
+            if not node:
+                return 0
+            s = node.val + dfs(node.left) + dfs(node.right)
+            self.best = max(self.best, s * (total - s))
+            return s
+
+        dfs(root)
+        return self.best % (10**9 + 7)
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    r1 = leetcode.treenode_build(vals=[1, 2, 3, 4, 5, 6])
+    r2 = leetcode.treenode_build(vals=[1, None, 2, 3, 4, None, None, 5, 6])
+    print(obj.maxProduct(r1))
+    print(obj.maxProduct(r2))