我们可以利用一下查找二叉树的性质.左子树的所有值小于根节点,右子树的所有值大于根节点.
所以如果求 1...n 的所有可能.
如果只有一个数字,那么所有可能就是一种情况,把该数字作为一棵树.而如果是 [ ],那就返回 null.
对于这道题,我们会更简单些,只需要返回树的数量即可.求当前根的数量,只需要左子树的数量乘上右子树.
然后,由于递归的分叉,所以会导致很多重复解的计算,所以使用 memoization 技术,把递归过程中求出的解保存起来,第二次需要的时候直接拿即可.
这道题,为什么和卡塔兰数列联系起来呢?
看一下卡塔兰树数列的定义:
上道题会了以后,这道题很好写.解法二中利用对称的优化,解法三的公式太强了.