LeetCode 解題筆記：823. Binary Trees With Factors

作者：王一哲
日期：2026年10月22日


LeetCode 題目連結：823. Binary Trees With Factors

解題想法

中等難度題。題目給一個長度為 $n ~(1 \leq n \leq 1000)$ 、數字不重複的整數陣列 $arr ~(2 \leq arr[i] \leq 10^9)$，用這些整數組成二元樹，且除了葉節點之外，其它節點的值必須等於其子節點值的乘積，計算共有幾種排列方式。由於答案很大，將排列方式對 $10^9 + 7$ 取餘數。

這題考動態規畫。先將 $arr$ 由小到大排序，因為計算特定乘積的排列方式數量時，需要用到較小乘積的排列方式數量。接下來用字典 $dp$ 記錄乘積 $v$ 當作根節點有幾種二元樹排列方式，由於更新數值時需要將兩個因數對應的值相乘，可能會超出 int 的上限，用 long 儲存會比較安全。用一個 for 迴圈跑 $arr[0]$ ~ $arr[n-1]$，先設定 $dp[arr[i]] = 1$，代表只有根節點時方法數為 $1$；再用一個 for 迴圈跑 $arr[0]$ 到 $arr[i-1]$，如果 $arr[j]$ 是 $arr[i]$ 的因數，則 $dp[arr[i]]$ 的方法數要再加上兩個因數的方法數乘積，同時對 $10^9 + 7$ 取餘數。每次計算完 $dp[arr[i]]$ 時立刻更新答案 $ans$。這個寫法的效率不算很好，但是比較容易理解。

Python 程式碼

Runtime: 229 ms, beats 16.59%. Memory: 20.68 MB, beats 5.68%.

class Solution:
    def numFactoredBinaryTrees(self, arr: list[int]) -> int:
        mod = 10**9 + 7
        n = len(arr)  # 長度
        arr.sort()  # 由小到大排序
        ans = 0  # 答案
        dp = defaultdict(int)  # 數字 v 當作根節點有幾種二元樹組合

        for i in range(n):  # 跑 arr[0] ~ arr[n-1]
            dp[arr[i]] = 1  # 以 arr[i] 當作根節點且樹只有根節點，1 種組合
            for j in range(i):  # 找出 arr[i] 的因數
                if arr[i] % arr[j] == 0:  # arr[j] 是因數
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] // arr[j]]) % mod  # 加上兩個因數組合數的乘積
            ans = (ans + dp[arr[i]]) % mod  # 更新答案
        return ans

C++ 程式碼

Runtime: 49 ms, beats 18.32%. Memory: 20.45 MB, beats 8.19%.

class Solution {
public:
    int numFactoredBinaryTrees(vector<int>& arr) {
        const int mod = 1000000007;
        int n = (int)arr.size(), ans = 0;  // 長度，答案
        sort(arr.begin(), arr.end());  // 由小到大排序
        unordered_map<int, long> dp;  // 數字 v 當作根節點有幾種二元樹組合

        for(int i = 0; i < n; i++) {  // 跑 arr[0] ~ arr[n-1]
            dp[arr[i]] = 1;  // 以 arr[i] 當作根節點且樹只有根節點，1 種組合
            for(int j = 0; j < i; j++) {  // 找出 arr[i] 的因數
                if (arr[i] % arr[j] == 0) {  // arr[j] 是因數
                    dp[arr[i]] = (dp[arr[i]] + dp[arr[j]] * dp[arr[i] / arr[j]] % mod) % mod;  // 加上兩個因數組合數的乘積
                }
            }
            ans = (ans + dp[arr[i]]) % mod;  // 更新答案
        }
        return ans;
    }
};