823. Binary Trees With Factors

Question

Given an array of unique integers, arr, where each integer arr[i] is strictly greater than 1.

We make a binary tree using these integers, and each number may be used for any number of times. Each non-leaf node’s value should be equal to the product of the values of its children.

Return the number of binary trees we can make. The answer may be too large so return the answer modulo 10<sup>9</sup><span> </span>+ 7.

Solution

根据题意，二叉树的根是两个子节点的乘积，因此一个根节点可组成的二叉树总数，相当于其左子节点可组成的二叉树总数，乘以其右子节点可组成的二叉树总数。

因此我们可以先将数组arr排序，用dp[]数组记录以从小到大的数字作为根节点可组成的最大二叉树总数。

由于每个根节点至少可以和自身组成一个节点，因此将dp[]数组初始化为1。

动态规划

从小到大遍历dp[]数组。
在遍历时，从遍历数值i的左侧选取当前位置的子节点。（根据题意子节点一定小于根节点）
当当前位置arr[i]可以整除arr[left]时，则有可能存在另一个子节点。此时根据哈希表中获得对应的另一个子节点right。如果right存在，则dp[i]更新为dp[i]+dp[left]*dp[right]的值。

最后将dp[]数组中记录的所有数字加和并返回。

Code

class Solution {
    public int numFactoredBinaryTrees(int[] arr) {
        final int MOD = (int) Math.pow(10, 9) + 7;
        Arrays.sort(arr);   //from minium to maxium
        HashMap<Integer, Integer> map = new HashMap<>();
        
        for(int i = 0; i < arr.length; i++){
            map.put(arr[i], i);
        }
        
        long[] dp = new long[arr.length];
        Arrays.fill(dp, 1);
        
        for(int i = 0; i < arr.length; i++){
            for(int left = 0; left < i; left++){
                if(arr[i] % arr[left] == 0){   //make sure divisible
                    int k = arr[i] / arr[left];
                    if(map.containsKey(k)){
                        int right = map.get(k);
                        dp[i] = (dp[i] + dp[left] * dp[right]) % MOD; 
                    }
                }
            }
        }
        
        int res = 0;
        
        for(long num : dp){
            res += num;
            res %= MOD;
        }
        
        return (int) res;
    }
}