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
本题要求对于给定的结点数,求出二叉搜索树的个数。二叉搜索树要求中序排列结果为非降序排列。
可以用动态规划的方法求解。
以结点数n=3为例,可以有三种组合形式:左子树有两个结点,右子树为空;左子树1个结点,右子树1个结点;左子树为空,右子树2个结点。那么3个结点的二叉搜索树种类就是这三种情况的加和。
每一种情况又是左子树的情况数乘以右子树的情况数。以第一种情况为例,也就是结点数为空的种类数乘以结点数为2的种类数。
初始条件当n=0和n=1时组合数均为1。
用数组dp对二叉搜索树的组合数进行维护。具体代码如下:
class Solution { public: int numTrees(int n) { vector<int> dp(n+1); dp[0]=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]; } } return dp[n]; } };