1339.分裂二叉树的最大乘积

链接：1339.分裂二叉树的最大乘积
难度：Medium
标签：树、深度优先搜索、二叉树
简介：给你一棵二叉树，它的根为 root 。请你删除 1 条边，使二叉树分裂成两棵子树，且它们子树和的乘积尽可能大。 。

题解 1 - typescript

• 编辑时间：2021-08-14
• 执行用时：184ms
• 内存消耗：63.9MB
• 编程语言：typescript
• 解法介绍：寻找最接近 sum/2 的值。

function maxProduct(root: TreeNode): number {
  const map = new Map<TreeNode, number>();
  const sum = dfsSum(root);
  let ans = 0;
  dfsNode(root);
  return ((sum - ans) * ans) % (10 ** 9 + 7);
  function dfsSum(node: TreeNode | null): number {
    if (node === null) return 0;
    const sum = dfsSum(node.left) + dfsSum(node.right) + node.val;
    map.set(node, sum);
    return sum;
  }
  function dfsNode(node: TreeNode | null): void {
    if (node === null) return;
    if (Math.abs(sum / 2 - ans) > Math.abs(sum / 2 - map.get(node!)!)) {
      ans = map.get(node!)!;
    }
    dfsNode(node.left);
    dfsNode(node.right);
  }
}