题解 | 二叉树的个数

import java.math.BigInteger;
import java.util.*;

/**
 * NC150 二叉树的个数
 * @author d3y1
 */
public class Solution {
    private final int MOD = 1000000007;

    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 
     * 相似 -> NC310 不同的二叉搜索树(一) [nowcoder]
     *
     * 计算二叉树个数
     * @param n int整型 二叉树结点个数
     * @return int整型
     */
    public int numberOfTree (int n) {
        return solution0(n);
        // return solution1(n);
        // return solution2(n);
        // return solution3(n);
        // return solution4(n);
        // return solution5(n);
    }

    /**
     * 动态规划
     *
     * 画图举例子找规律!
     *
     * T[n]表示节点个数为n时的树形种数
     *
     * @param n
     * @return
     */
    private int solution0(int n){
        // T -> Type(树形)
        long[] T = new long[n+1];

        T[0] = 1;
        for(int i=1; i<=n; i++){
            for(int j=0; j<i; j++){
                // T[i] = ((T[i]+T[j]*T[(i-1)-j])%MOD);
                T[i] += T[j]*T[(i-1)-j];
                T[i] %= MOD;
            }
        }

        return (int) T[n];
    }

    /**
     * 动态规划
     *
     * 画图举例子找规律:
     *
     * dp[i][j]表示总节点数为i且以节点j为根节点时构成互不相同二叉搜索树的方法数
     * C[i]表示总节点数为i时构成互不相同二叉搜索树的方法数
     *
     * // 固定根节点j 左子树还有j-1个节点(方法数为C[j-1]) 右子树还有i-j个节点(方法数为C[i-j])
     * dp[i][j] = C[j-1] * C[i-j]
     * // 分别以各个节点为根节点
     * C[i] = dp[i][1] + dp[i][2] + ... + dp[i][i-1] + dp[i][i]  , 2<=i<=n && 1<=j<=i
     *      = C[1-1] * C[i-1] + C[2-1] * C[i-2] + ... + C[(i-1)-1] * C[i-(i-1)] + C[i-1] * C[i-i]
     *      = C[0] * C[i-1] + C[1] * C[i-2] + ... + C[i-2] * C[1] + C[i-1] * C[0]
     *
     * @param n
     * @return
     */
    private int solution1(int n){
        long[] C = new long[n+1];
        long[][] dp = new long[n+1][n+1];

        C[0] = 1;
        C[1] = 1;
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i; j++){
                dp[i][j] = C[j-1] * C[i-j];
                C[i] += dp[i][j];
                C[i] %= MOD;
            }
        }

        return (int) C[n];
    }

    /**
     * 动态规划: 简化
     *
     * 画图举例子找规律:
     *
     * C[i]表示总节点数为i时构成互不相同二叉搜索树的方法数
     * C[i] = C[0] * C[i-1] + C[1] * C[i-2] + ... + C[i-2] * C[1] + C[i-1] * C[0]  , 2<=i<=n && 1<=j<=i
     *
     * @param n
     * @return
     */
    private int solution2(int n){
        long[] C = new long[n+1];

        C[0] = 1;
        C[1] = 1;
        for(int i=2; i<=n; i++){
            for(int j=1; j<=i; j++){
                C[i] +=  C[j-1] * C[i-j];
                C[i] %= MOD;
            }
        }

        return (int) C[n];
    }

    /**
     * 数学法
     *
     * 画图举例子找规律:
     *
     * C[i]表示总节点数为i时构成互不相同二叉搜索树的方法数(C[0] = C[1] = 1)
     * C[i] = C[0] * C[i-1] + C[1] * C[i-2] + ... + C[i-2] * C[1] + C[i-1] * C[0]  , 2<=i<=n && 1<=j<=i
     *
     * 可见:
     * C[0] = 1
     * C[1] = 1
     * C[2] = 2
     * C[3] = 5
     * C[4] = 14
     * C[5] = 42
     * C[6] = 132
     * ...
     *
     * 以上为卡塔兰数
     * C[n] = C(n) = (2n)! / ((n+1)!n!)
     *
     * @param n
     * @return
     */
    private int solution3(int n){
        return C(n).intValue();
    }

    /**
     * C(n)
     * @param n
     * @return
     */
    private BigInteger C(int n){
        BigInteger up = new BigInteger("1");
        BigInteger down = new BigInteger("1");

        for(int i=1; i<=n; i++){
            if(i < n){
                up = up.multiply(BigInteger.valueOf(n+1+i));
            }
            down = down.multiply(BigInteger.valueOf(i));
        }

        return up.divide(down).mod(BigInteger.valueOf(MOD));
    }

    /**
     * 数学法
     *
     * 画图举例子找规律:
     *
     * C[i]表示总节点数为i时构成互不相同二叉搜索树的方法数(C[0] = C[1] = 1)
     * C[i] = C[0] * C[i-1] + C[1] * C[i-2] + ... + C[i-2] * C[1] + C[i-1] * C[0]  , 2<=i<=n && 1<=j<=i
     *
     * 可见:
     * C[0] = 1
     * C[1] = 1
     * C[2] = 2
     * C[3] = 5
     * C[4] = 14
     * C[5] = 42
     * C[6] = 132
     * ...
     *
     * 以上为卡塔兰数
     * C[n] = C(n) = C(n-1)*(4n-2)/(n+1)
     *
     * @param n
     * @return
     */
    private int solution4(int n){
        long[] C = new long[n+1];
        // 逆元(因为结果非常大, 所以题目要求将结果取模. 因为涉及除法, 所以需要引入逆元)
        long[] inv = new long[n+2];

        C[0] = 1L;
        inv[1] = 1;
        inv[2] = MOD-MOD/2;
        for(int i=1; i<=n; i++){
            // C[i] = (C[i-1]*(4*i-2)/(i+1))%MOD;
            inv[i+1] = (MOD-MOD/(i+1)) * inv[MOD%(i+1)]%MOD;
            C[i] = C[i-1]*(4*i-2)%MOD * inv[i+1]%MOD;
        }

        return (int) C[n];
    }

    private long[] memo;

    /**
     * 递归 + 记忆法memo
     * @param n
     * @return
     */
    private int solution5(int n){
        memo = new long[n+1];
        return (int) dfs(n);
    }

    /**
     * 递归
     * @param n
     * @return
     */
    private long dfs(int n){
        if(memo[n] != 0){
            return memo[n];
        }
        if(n==0 || n==1){
            return 1;
        }

        long result = 0L;
        long left,right;
        for(int i=1; i<=n; i++){
            // 左子树 树形种数
            left = dfs(i-1);
            // 右子树 树形种数
            right = dfs(n-i);

            result = (result+left*right)%MOD;
        }

        memo[n] = result;

        return result;
    }
}