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

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

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

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

输入描述:

第一行输入一个整数 n。

输出描述:

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

示例1

输入

输出

备注:

算法知识视频讲解

皮蛋秀柚秋

#include<bits/stdc++.h>
using namespace std;
int main()
{
    //当节点个数n确定时 能组成的二叉树结构个数也是确定的
    // n个节点中1，2，...n均可做根节点
    // ans = f(1) + f(2) + ... + f(n)  f(i)表示当i做根节点时有几种结构
    // i为根，则说明左子树有i-1个节点，右子树有n-i个节点 f(i) = f(i-1) * f(n-i)
    // 存在重叠子问题，可dp解决
    int n;
    cin>>n;
    int mod = 1e9 + 7;
    vector<long>dp(n+1,0);
    dp[0] = 1;
    dp[1] = 1;
    for(int i=2;i<=n;++i)
    {
        for(int j=0;j<i;++j)
        {
            dp[i] += ((dp[j]%mod) * (dp[i-j-1]%mod));
            dp[i]%=mod;

        }

    }
    cout<<dp[n];
    return 0;
}

发表于 2020-02-07 21:44:30 回复(0)

pein531

假设二叉树有n个节点，编号从i开始，如果i为根节点，则1~i-1就是其左子树，i+1~n就是右子树，整棵树的结构数量=左子树的结构数量*右子树的结构数量。计dp[i]为有i个节点时二叉树的结构数量，则可以遍历根节点j的可能性0 <= j <= i，把每种树的结构树累加起来。于是得到状态转移方程：

$dp[i]= \sum_{j=0}^{i-1} {dp[j]*dp[i-j-1]}$

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    final static int MOD = 1000000007;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        long[] dp = new long[n + 1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2; i <= n; i++) {
            for(int j = 0; j < i; j++){
                dp[i] += dp[j] * dp[i - j - 1];
                dp[i] %= MOD;
            }
        }
        System.out.println(dp[n]);
    }
}

发表于 2021-11-19 14:38:36 回复(0)

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)

等商汤mc的白菜苗

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(int argc, char** argv){
	int n;
	while(cin >> n){
		vector<long long> temp(n+1, 0);
		temp[0] = 1;
		temp[1] = 1;
		temp[2] = 2;
		for(int i = 3; i <= n; i++){
			for(int j = 0; j < i; j++){
//				cout << j << " " << i-j-1 << endl;
				temp[i] += temp[j] * temp[i - j - 1];
				temp[i] = temp[i] % (1000000007);
			}
		}
		cout << temp[n] << endl;
	}
	return 0;
}

发表于 2019-09-13 16:02:14 回复(0)

keepgoing20190801113019

#include <iostream>
#include <string>
#include <cmath>
using namespace std;

long long tab[10001]={0} ;
long long makeTree(int start, int end)
{
if (tab[end-start] != 0)
return tab[end-start];

if (start==end)
{
tab[end-start] = 1;
return 1;
}
else if (end-start==2)
{
tab[end-start] = 5;
return 5;
}

long long ret=0;
for (int i=start; i<=end; i++)//choose one as root.
{
if (i==start)
ret+=makeTree(i+1, end);
else if (i==end)
ret+=makeTree(start, i-1);
else
{
long long left=makeTree(start, i-1);
long long right=makeTree(i+1, end);
long long tmp=left*right%1000000007;
ret += tmp;
}
}
ret %= 1000000007;
tab[end-start]=ret;
return ret;
}

int main()
{
int n;
cin>>n;
long long ret=makeTree(1, n);
cout<<ret;
return 0;
}

发表于 2019-08-04 00:21:19 回复(0)