182 统计和生成所有不同的二叉树
Table of Contents

ac

前几项为:1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, 58786, 208012

O(n^2)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

class TreeNode{
    TreeNode left;
    TreeNode right;
    int val;

    public TreeNode(int val) {
        this.val = val;
        left = null;
        right = null;
    }
}

public class Main {
    public static Scanner sc = new Scanner(System.in);

    public static BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));

    public static int mod = 1000000007;

    public static int N = 10001;

    public static void main(String[] args) throws Exception {
        int n = sc.nextInt();
        System.out.print(rev(n));
    }

    static long rev(int n){
        // 0 处理成 1
        long[] arr = new long[N];
        arr[0] = 1;
        arr[1] = 1;
        arr[2] = 2;
        if(n <= 2){
            return arr[n];
        }
        for(int k=3;k<=n;k++) {
            long sum = 0;
            for (int i = 0; i < k; i++) {
                int leftCnt = i;
                int rightCnt = k - i - 1;
                sum += arr[leftCnt] * arr[rightCnt];
                sum %= mod;
            }
            arr[k] = sum;
        }
        return arr[n];
    }

}
/*
结构
  2  1
 /    \
1      2

7

429

43

4616923
 */