Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1339.html
1339. Maximum Product of Splitted Binary Tree (Medium)
Given a binary tree root
. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: root = [1,2,3,4,5,6] Output: 110 Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
Example 2:
Input: root = [1,null,2,3,4,null,null,5,6] Output: 90 Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)
Example 3:
Input: root = [2,3,9,10,7,8,6,5,4,11,1] Output: 1025
Example 4:
Input: root = [1,1] Output: 1
Constraints:
- Each tree has at most
50000
nodes and at least2
nodes. - Each node's value is between
[1, 10000]
.
Related Topics:
Dynamic Programming, Tree
Solution 1.
-
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { public int maxProduct(TreeNode root) { final int MODULO = 1000000007; List<TreeNode> nodesList = new ArrayList<TreeNode>(); Map<TreeNode, TreeNode> childParentMap = new HashMap<TreeNode, TreeNode>(); Queue<TreeNode> queue = new LinkedList<TreeNode>(); queue.offer(root); while (!queue.isEmpty()) { TreeNode node = queue.poll(); nodesList.add(node); TreeNode left = node.left, right = node.right; if (left != null) { childParentMap.put(left, node); queue.offer(left); } if (right != null) { childParentMap.put(right, node); queue.offer(right); } } for (int i = nodesList.size() - 1; i > 0; i--) { TreeNode node = nodesList.get(i); TreeNode parent = childParentMap.get(node); if (parent != null) parent.val += node.val; } long maxProduct = 0; for (int i = nodesList.size() - 1; i > 0; i--) { TreeNode node = nodesList.get(i); int value1 = node.val, value2 = root.val - node.val; long product = (long) value1 * (long) value2; maxProduct = Math.max(maxProduct, product); } int maxProductModulo = (int) (maxProduct % MODULO); return maxProductModulo; } } ############ /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; * } * } */ class Solution { private long ans; private long s; private static final int MOD = (int) 1e9 + 7; public int maxProduct(TreeNode root) { s = sum(root); dfs(root); ans %= MOD; return (int) ans; } private long sum(TreeNode root) { if (root == null) { return 0; } return root.val + sum(root.left) + sum(root.right); } private long dfs(TreeNode root) { if (root == null) { return 0; } long t = root.val + dfs(root.left) + dfs(root.right); if (t < s) { ans = Math.max(ans, t * (s - t)); } return t; } }
-
// OJ: https://leetcode.com/problems/maximum-product-of-splitted-binary-tree/ // Time: O(N) // Space: O(H) class Solution { long total = 0, ans = 0, mod = 1e9 + 7; void sum(TreeNode *root) { if (!root) return; total += root->val; sum(root->left); sum(root->right); } long dfs(TreeNode *root) { if (!root) return 0; long s = root->val + dfs(root->left) + dfs(root->right); ans = max(ans, (total - s) * s); return s; } public: int maxProduct(TreeNode* root) { sum(root); dfs(root); return ans % mod; } };
-
# Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def maxProduct(self, root: Optional[TreeNode]) -> int: def sum(root): if root is None: return 0 return root.val + sum(root.left) + sum(root.right) def dfs(root): nonlocal s, ans if root is None: return 0 t = root.val + dfs(root.left) + dfs(root.right) if t < s: ans = max(ans, t * (s - t)) return t s = sum(root) ans = 0 dfs(root) ans %= 10**9 + 7 return ans
-
/** * Definition for a binary tree node. * type TreeNode struct { * Val int * Left *TreeNode * Right *TreeNode * } */ func maxProduct(root *TreeNode) int { mod := int(1e9) + 7 var sum func(*TreeNode) int sum = func(root *TreeNode) int { if root == nil { return 0 } return root.Val + sum(root.Left) + sum(root.Right) } s := sum(root) ans := 0 var dfs func(*TreeNode) int dfs = func(root *TreeNode) int { if root == nil { return 0 } t := root.Val + dfs(root.Left) + dfs(root.Right) if t < s { ans = max(ans, t*(s-t)) } return t } dfs(root) return ans % mod } func max(a, b int) int { if a > b { return a } return b }
-
/** * Definition for a binary tree node. * class TreeNode { * val: number * left: TreeNode | null * right: TreeNode | null * constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } * } */ function maxProduct(root: TreeNode | null): number { const sum = (root: TreeNode | null): number => { if (!root) { return 0; } return root.val + sum(root.left) + sum(root.right); }; const s = sum(root); let ans = 0; const mod = 1e9 + 7; const dfs = (root: TreeNode | null): number => { if (!root) { return 0; } const t = root.val + dfs(root.left) + dfs(root.right); if (t < s) { ans = Math.max(ans, t * (s - t)); } return t; }; dfs(root); return ans % mod; }