给定一个整数 n,求以 1 ... n 为节点组成的二叉搜索树有多少种?

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

 

思路;

/*
     * 既然是二叉搜索树 那么中序的结果为1 2 3 . . . n
     * 根据二叉搜索树可以知道,某根节点x,它的左子树的值全<=x(当然本题不存在等于的情况),它的右子树的值全>=x, 所以,当它的根节点是 1
     * 的时候,左子树个数为 0 ,右子树的个数为 n-1, 当它的根节点为 2 的时候, 左子树个数为 1, 右子树的个数为 n-2…… x-1个 x n-x个
     * 还有一个规律,就是这棵树的不同形态的二叉查找树的个数,就是根节点的 左子树的个数*右子树的个数,想想还是很
     * 容易理解的,就是左边的所有情况乘以右边的所有情况 动态规划,dp[i]从前到后计算出当有i个节点时,它有多少种不同形态的树
     */

    /*
     * 就跟斐波那契数列一样,我们把n = 0 时赋为1,因为空树也算一种二叉搜索树,那么n = 1时的情况可以看做是其左子树个数乘以右子树的个数,
     * 左右字数都是空树,所以1乘1还是1。那么n = 2时,由于1和2都可以为跟,分别算出来,再把它们加起来即可
     */

 

public static int numTrees(int n) {
		if (n == 0)
			return 0;
		if (n == 1)
			return 1;
		int[] dp = new int[n + 1];
		dp[0] = 1;
		dp[1] = 1;
		// 当节点个数为0时有一种形态的树(也就是空树吧),当节点个数为1时有一种形态的树,之后就可以向下继续计算节点为2,3,4,5,……n
		for (int i = 2; i <= n; i++) { //控制有多少个节点
			for (int j = 0; j < i; j++) {
				//  dp[j] * dp[i-1-j]为新加的j作为根节点 得到的情况数
				dp[i] = dp[i] + dp[j] * dp[i - 1 - j];
			}
		}
		return dp[n];
	}