试题 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中所有的数作为根节点。因为根节点不同所以可以对数量求和。 当以m为根节点，那么小于m的一定在左子树，大于m的一定在右子树。这样的话我们可以用左子树的方案数*右子树方案数来获得以m为根节点的方案数量。而左子树或右子树的方案数问题又回归到了原问题。另外一个注意点是无需考虑节点数值大小，而只需考虑个数。也就是代码中n-i。 为了降低重复计算，可以使用数组存储。
递归原版：
class Solution { public int numTrees(int n) { if(n==0) return 1; int tmp = 0; for(int i=1; i<=n; i++){ tmp += numTrees(i-1) * numTrees(n-i); } return tmp; } }超时优化：
class Solution { public int numTrees(int n) { int[] mem = new int[n+1]; mem[0] = 1; return numTrees(n, mem); } private int numTrees(int n, int[] mem){ if(mem[n]!=0) return mem[n]; for(int i=1; i<=n; i++){ mem[n] += numTrees(i-1, mem) * numTrees(n-i,mem); } return mem[n]; } }