LeetCode | 带因子的二叉树

带因子的二叉树

给出一个含有不重复整数元素的数组 arr ，每个整数 arr[i] 均大于 1。
用这些整数来构建二叉树，每个整数可以使用任意次数。其中：每个非叶结点的值应等于它的两个子结点的值的乘积。
满足条件的二叉树一共有多少个？答案可能很大，返回 对 109 + 7 取余 的结果。

主要方法和思路：递归化为子问题，然后通过记忆化搜索，剪枝进行优化

我们可以把数组的每个数作为根节点，然后看数组中是否可以找到两个数可以作为他的因子（可以通过map来寻找），之后每个因子都是同样的操作，所以就化为了子问题，可以通过递归来解决，左右子树相乘得到总数量。

另外来说，因为可能有个数需要进行重复计算，所以可以用一个数组来记录已经计算过的

func numFactoredBinaryTrees(arr []int) int {
    m := len(arr)
    // if m <= 1 {
    //     return m
    // }
    // sort.Ints(arr)
    // 思路，通过分解成子问题

    // 判断 以这个数 为根节点 有多少棵树
    // 首先是单独 自己，然后看 是否有因子，有的话看是否有另一个因子可以相乘等于 自己的
    mm := make(map[int]int, m)
    for k, v := range arr {
        mm[v] = k
    }
    // 数组 记忆
    use := make([]int, m)
    for i := range use {
        use[i] = -1
    }
    var dfs func(a int) int
    dfs = func(a int) int {
        res := 1
        val := arr[a]
        p := &use[a]
        // 剪枝
        if *p != -1 {
            return *p
        }
        // 如果有因子
        for k, v := range arr {
            if val%v == 0 { 
                if i, ok := mm[val/v]; ok {
                    res += dfs(k) * dfs(i)
                }
            }
        }
        *p = res
        return res
    }
    ans := 0
    // 遍历数组
    for k := range arr {
        ans += dfs(k)
    }
    return ans % 1000000007
}