[LeetCode]Unique Binary Search Trees II

很I非常类似，递归的做法非常明显。对于1-i的数，每个数k可以作为根，那么对于左子树，generate[1, k - 1]的所有可能，对于右子树，generate[k + 1, i]的所有可能，然后分别和root连上即可。代码如下：



当然递归的方法包含了太多的重复计算，我们可以用DP来优化，DP[i]存[1, i]组成的所有BST的可能。如果我们找左子树的所有可能，直接去DP数组取即可。如果是右子树，比如[m, n]的所有BST可能，我们只要把[1, n - m + 1]的所有结果向右平移然后clone新的BST出来即可。T(n) = T(0)T(n - 1) + T(1)T(n - 2) + ... +T(n - 1)T(0)，时间复杂度为Catalan Number，C(n) = (2n)!/((n + 1)!n!) 。空间复杂度的话，虽然我们不clone左子树，但是我们每次还是要给右子树分配额外的空间，用C(i)表示Catalan Number的第i个数，空间复杂度为C(1) + C(2) + ... + C(n) = O(C(n))。代码如下：