首页 > 试题广场 >

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

[编程题]统计和生成所有不同的二叉树
  • 热度指数:3289 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
给出一个整数 n,如果 n < 1,代表空树,否则代表中序遍历的结果为 {1, 2, 3... n}。请输出可能的二叉树结构有多少。

输入描述:
第一行输入一个整数 n。


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

输入

7 

输出

429 

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