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 least 2 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;
}

1339 - Maximum Product of Splitted Binary Tree

1339. Maximum Product of Splitted Binary Tree (Medium)

Solution 1.

All Problems

All Solutions

Welcome to Subscribe On Youtube

1339. Maximum Product of Splitted Binary Tree (Medium)

Solution 1.

All Problems

All Solutions