统计和生成所有不同的二叉树

[编程题]统计和生成所有不同的二叉树

热度指数：3289 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给出一个整数 n，如果 n < 1，代表空树，否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。

输入描述:

第一行输入一个整数 n。

输出描述:

输出一个整数对 1e9 + 7 取模的值表示答案。

示例1

输入

输出

备注:

算法知识视频讲解

查看答案及解析

Java

最近学习速度慢的渣渣

1.注意数据结构用long 不然中途溢出再取模就不会发现了然后算个错误结果

2.取模由于没做过竞赛题第一次碰，刚开始看成了e的9次方+7 ....

3.写的比较烂也没优化轻喷跟踪这个溢出bug花了太久时间

import java.util.Scanner;

public class Main {
       public int howManyTrees(int n) {
        if (n < 1) return 0;
        else if (n == 1) return 1;
        else if (n == 2) return 2;
        else {
            int mod = (int) 1e9 + 7;
            long[] num = new long[n + 1];
            num[0] = 1;
            num[1] = 1;
            for (int i = 2; i < n + 1; i++) {
                num[i] = 0;
                for (int j = 0; j < i; j++) {
                    num[i] = num[i] + (num[j] * num[i - 1 - j]) % mod;
                    num[i] %= mod;
                }
            }
            return (int)num[n];
        }
    }

    public static void main(String[] args) {
        Main main = new Main();
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        System.out.println(main.howManyTrees(n));
    }
}

发表于 2020-03-04 16:58:12 回复(0)