豆包 LeetCode 1916.统计为蚂群构筑房间的不同顺序 TypeScript实现

LeetCode 1916 统计为蚁群构筑房间的不同顺序 TypeScript 实现
 
核心思路
 
与Java版完全一致：树形DP + 组合数学（阶乘逆元）
 
- 问题本质：求有根树的拓扑排序数量（父节点必须在子节点之前）
- 核心公式：对于节点u，其拓扑数 = 所有子树拓扑数 × 子树间排列组合数的乘积
- 组合数计算：使用费马小定理预处理阶乘和逆元阶乘，O(1)查询
- 迭代后序遍历：避免TypeScript递归深度限制（n=1e5链状树不会栈溢出）
 
完整TypeScript代码
 
typescript   
function waysToBuildRooms(prevRoom: number[]): number {
    const MOD = 1000000007n;
    const n = prevRoom.length;

    // 1. 构建树的邻接表
    const children: number[][] = Array.from({ length: n }, () => []);
    for (let i = 1; i < n; i++) {
        children[prevRoom[i]].push(i);
    }

    // 2. 预处理阶乘和逆元阶乘（使用BigInt避免精度丢失）
    const fact: bigint[] = new Array(n);
    const invFact: bigint[] = new Array(n);
    fact[0] = 1n;
    f