96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5

题目

给定一个整数，表示为节点数目，问能有几种二分搜索树的组合。

思路

没有思路。。。。
看了网上讲解，才知道这个数列叫做卡塔兰数，但是无论知道与否，可以总结一下这个数列的规律。
回到题目，

• 当n=0时，我们把他也当做一种形式，空树，记为n=0时，BST=1;
• 当n=1时，左边可以有0个节点，右边也可以有0个节点，所以只有一种情况，记为n=1时，BST=1;
• 当n=2时，可以让1为根，此时左边为0个节点，右边为1个节点，这是一种情况；还可以让2为根，那此时只能是左边为1，右边没有，所以加起来，一共有2种情况。记为n=2时，BST=2;
• 当n=3时，根节点分别可以为1、2、3，当1为根时，左边不可以有节点，右边可以有两个节点，这两个节点属于n=2的情况，即有2种可能的树，所以根为1时，可以有左边×右边=1×2种情况；同理根为3时，也是1×2种情况；再来看根为2，最简单了，左右各有一个节点，所以就一种情况；综上，再把根为1、2、3的所有情况加起来，即2+1+2=5，记为n=3时，BST=5;
  -当n=4时，快速算一下，即1、2、3、4分别为根时，1为根：左边没有节点，右边有3个节点；2为根，左边有1个右边有2个；3为根，左边2个右边1个，4为根，左边3个，右边没有。综上，一共1×5+1×2+2×1+5×1=14种。
• 当n=5时，不算了。。。

照此总结出来就是卡特兰数列的递推公式。
所以我们可以整理成代码如下：

代码

public class Solution {
    Map<Integer, Integer> cache= new HashMap<>();//缓存，避免大量重复计算，把算过的存在map里
     public int numTrees(int n) {
         if (cache.containsKey(n)) {
            return cache.get(n);
        }
         int res=0;
         if (n==0) {
             res=1;
            return res;
        }
         for (int i = 0; i <n; i++) {//把每一个数当根节点的可能相加，res就是最后的值
            res=res+numTrees(i)*numTrees(n-1-i);
        }
         cache.put(n,res);
        return res;
        }
    @Test
    public void test1() {
        System.out.println(numTrees(5));
    }

}