Skip to content

823-带因子的二叉树.md

Latest commit

 

History

History
36 lines (27 loc) · 970 Bytes

823-带因子的二叉树.md

File metadata and controls

36 lines (27 loc) · 970 Bytes
Raw

823-带因子的二叉树

原题

给出一个含有不重复整数元素的数组，每个整数均大于 1。

我们用这些整数来构建二叉树，每个整数可以使用任意次数。

其中：每个非叶结点的值应等于它的两个子结点的值的乘积。

满足条件的二叉树一共有多少个？返回的结果应模除 10 ** 9 + 7。

var numFactoredBinaryTrees = function (A) {
  A.sort((a, b) => a - b);
  const map = {};
  A.forEach((v) => (map[v] = 1));

  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j <= i; j++) {
      if (map[A[i] * A[j]]) {
        let curI = map[A[i]];
        let curJ = map[A[j]];

        if (i == j) {
          map[A[i] * A[j]] += curI * curJ;
        } else {
          map[A[i] * A[j]] += curI * curJ * 2;
        }
      }
    }
  }

  return Object.values(map).reduce((v, c) => c + v) % (10 ** 9 + 7);
};