题目描述

给定一个整数 n，生成所有由 1 ... n 为节点所组成的二叉搜索树。

示例：

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

递归思路

1.二叉搜索树的性质是根节点的左子树都比根节点小，根节点的右子树都比根节点大。
2.可以从二叉搜索树的性质看出，其定义与递归可以完美的契合。
3.我们可以编写一个函数，当我们选定i作为根节点时，function(start,i-1)为所有左子树数量，function(i+1,end)为所有右子树数量，二者的结果组合（相乘），便是以i作为根节点的所有二叉搜索树。

Java代码实现

    public int numTrees(int n){
        if(n<1)
            return n;
        return numTrees(1,n);
    }

    public int numTrees(int start,int end){
        if(start > end)
            return 1;

        int sum = 0;
        for (int i = start; i <= end ; i++) {
            int left = numTrees(start,i-1);
            int right = numTrees(i+1,end);
            sum = sum + left*right;
        }
        return sum;
    }

备忘录思路

1.我们可以发现存在节点的答案被计算了多次，所以可以使用一个备忘录，若该节点的答案已经被计算过了，便直接返回。

Java代码实现

    public int numTrees(int n){
        if(n<1)
            return n;
        Map<String,Integer> memory = new HashMap<>();
        return numTrees(1,n,memory);
    }

    public int numTrees(int start,int end,Map<String,Integer> memory){
        if(start > end)
            return 1;

        if(memory.containsKey(start+"-"+end))
            return memory.get(start+"-"+end);

        int sum = 0;
        for (int i = start; i <= end ; i++) {
            int left = numTrees(start,i-1,memory);
            int right = numTrees(i+1,end,memory);
            sum = sum + left*right;
        }
        memory.put(start+"-"+end,sum);
        return sum;
    }

动态规划思路

  1. 我们通过以上的思路可以发现，这道题的套路和动态规划是一致的（递归->备忘录->动态规划），所以我们只需要找到状态转移方程，便可以使用动态规划求解，大幅度降低执行时间。

2.下面我们进行状态转移方程的推导。

  • 假设我们有n个节点，那么他的组合个数应该等于1~n个节点当根节点的组合数总和，即：G(n) = f(1)+f(2)+f(3)+......+f(n)
  • 我们从递归的方法中可以发现：f(i) = G(i-1) + G(n-i)
  • 将两个公式结合后：G(n) = G(0)G(n-1)+G(1)G(n-2)+.....+G(n-1)G(0)
    其实这个公式就是大名鼎鼎的卡特兰数，有兴趣的同学可以去了解一下。

Java代码实现

    public int numTrees(int n){
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i = 2; i <=n ; i++) {
            for (int j = 1; j <=i ; j++) {
                dp[i] += dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }