解法一：DP
public class Solution { public int numTrees(int n) { int[] f = new int[n+1]; f[0] = 1; f[1] = 1; for (int len = 2; len <= n; len ++) for (int subLen = 0; subLen <= len - 1; subLen ++) // node of a left son f[len] += f[subLen] * f[len - subLen - 1]; // left-right -> right-left return f[n]; } }解法二： 递归遍历计算所有种类（注意用HashMap保存已有结果，否则会超时）
public class Solution { HashMap<Integer, Integer> num = new HashMap<Integer, Integer>(); //return the amount of structurally unique BST's that store values i..j public int numTrees(int start, int end){ if (num.containsKey(end-start)) return num.get(end-start); int count = 0; for (int i = start; i <= end; i ++){ //current root = i if (i == start) count += numTrees(i+1, end); else if (i == end) count += numTrees(start, i-1); else count += (numTrees(start, i-1) * numTrees(i+1, end)); } num.put(end-start, count); return count; } public int numTrees(int n) { num.put(0, 1); return numTrees(1, n); } }