96. Unique Binary Search Trees

题目描述

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3 Output: 5 Explanation: Given n = 3, there are a total of 5 unique BST's: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3题目大意：求[1,n]可以构造的所有不同的二叉搜索树

---

解题思路：

在给定的序列[1,n]下，我们来构造二叉搜索树，首先对于序列中的每个数我们都可以当根节点，对于任一确定的根节点，所能构造的二叉搜索树，

我们需要确定其左子树，右子树所能构成的二叉搜搜索树，不能看出本题具有递归性质，因为不同的根节点对应不同的数，所以我们可以确定所有的二叉搜索树

我们的目标是为了计算不同的二叉搜索树的个数，因此我们定义两个函数：

G（n）:n表示区间[1,n]之间，函数值表示在此区间下构成的不同二叉搜索树

F(i,n),1<=i<=n:表示在i为根节点，区间为[1,n]时可以构成的不同二叉搜索树

G（n）=F(1,n)+F(2,n).....+F(n,n)

特别的对G（0）=1，G（1）=0

对于特别的F(3,7)，左子树为[1,2],右子树为[4,5,6,7]

F(3,7)=G(2)*G(4)

因为[4,5,6,7]构成的数个数与[1,2,3,5]相同

所以：

G（n）=G(0)*G(n-1)+G(1)*G(i-2).....G(n-1)*G(0)

卡特兰数

G(n)由前n-1个G构成所有构造动态规划表达式

解题代码 class Solution { public: //卡特兰数的应用 int numTrees(int n) { int G[n+1]={0}; G[0]=G[1]=1; for(int i=2;i<=n;i++) { for(int j=0;j<=i-1;j++) { G[i]+=G[j]*G[i-j-1]; } } return G[n]; } };

　　

转载于:https://www.cnblogs.com/zydxx/p/10610202.html

相关资源：JAVA上百实例源码以及开源项目