Maximum Product of Splitted Binary Tree LeetCode solution in JavaScript

1
var maxProduct = function (root) {
2
  const lefteRightSumMap = new Map();
3

4
  function getLeftRightSumMap(node) {
5
    if (node === null) return 0;
6

7
    let leftSum = getLeftRightSumMap(node.left);
8
    let rightSum = getLeftRightSumMap(node.right);
9

10
    lefteRightSumMap.set(node, { leftSum, rightSum });
11

12
    return leftSum + rightSum + node.val;
13
  }
14

15
  getLeftRightSumMap(root);
16

17
  let maxProduct = -Infinity;
18

19
  function getMaxProductDFS(node, parentSum) {
20
    if (node === null) return;
21

22
    const { leftSum, rightSum } = lefteRightSumMap.get(node);
23

24
    // cut left edge
25
    maxProduct = Math.max(
26
      maxProduct,
27
      leftSum * (parentSum + node.val + rightSum)
28
    );
29

30
    // cut right edge
31
    maxProduct = Math.max(
32
      maxProduct,
33
      rightSum * (parentSum + node.val + leftSum)
34
    );
35

36
    getMaxProductDFS(node.left, parentSum + node.val + rightSum);
37
    getMaxProductDFS(node.right, parentSum + node.val + leftSum);
38
  }
39

40
  getMaxProductDFS(root, 0);
41

42
  return maxProduct % (Math.pow(10, 9) + 7);
43
};