给定一个整数 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];
	}