題目描述

給定一個(gè)整數(shù) n，生成所有由 1 ... n 為節(jié)點(diǎn)所組成的二叉搜索樹。

示例：

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:

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

遞歸思路

1.二叉搜索樹的性質(zhì)是根節(jié)點(diǎn)的左子樹都比根節(jié)點(diǎn)小，根節(jié)點(diǎn)的右子樹都比根節(jié)點(diǎn)大。
2.可以從二叉搜索樹的性質(zhì)看出，其定義與遞歸可以完美的契合。
3.我們可以編寫一個(gè)函數(shù)，當(dāng)我們選定i作為根節(jié)點(diǎn)時(shí)，function(start,i-1)為所有左子樹數(shù)量，function(i+1,end)為所有右子樹數(shù)量，二者的結(jié)果組合（相乘），便是以i作為根節(jié)點(diǎn)的所有二叉搜索樹。

Java代碼實(shí)現(xiàn)

    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.我們可以發(fā)現(xiàn)存在節(jié)點(diǎn)的答案被計(jì)算了多次，所以可以使用一個(gè)備忘錄，若該節(jié)點(diǎn)的答案已經(jīng)被計(jì)算過了，便直接返回。

Java代碼實(shí)現(xiàn)

    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;
    }

動(dòng)態(tài)規(guī)劃思路

1. 我們通過以上的思路可以發(fā)現(xiàn)，這道題的套路和動(dòng)態(tài)規(guī)劃是一致的（遞歸->備忘錄->動(dòng)態(tài)規(guī)劃），所以我們只需要找到狀態(tài)轉(zhuǎn)移方程，便可以使用動(dòng)態(tài)規(guī)劃求解，大幅度降低執(zhí)行時(shí)間。

2.下面我們進(jìn)行狀態(tài)轉(zhuǎn)移方程的推導(dǎo)。

• 假設(shè)我們有n個(gè)節(jié)點(diǎn)，那么他的組合個(gè)數(shù)應(yīng)該等于1~n個(gè)節(jié)點(diǎn)當(dāng)根節(jié)點(diǎn)的組合數(shù)總和，即：G(n) = f(1)+f(2)+f(3)+......+f(n)
• 我們從遞歸的方法中可以發(fā)現(xiàn)：f(i) = G(i-1) + G(n-i)
• 將兩個(gè)公式結(jié)合后：G(n) = G(0)G(n-1)+G(1)G(n-2)+.....+G(n-1)G(0)
  其實(shí)這個(gè)公式就是大名鼎鼎的卡特蘭數(shù)，有興趣的同學(xué)可以去了解一下。

Java代碼實(shí)現(xiàn)

    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];
    }