不同的二叉搜索樹(shù)

題目鏈接：https://leetcode-cn.com/problems/unique-binary-search-trees

給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹(shù)有多少種?

示例:

思路

這道題目描述很簡(jiǎn)短，但估計(jì)大部分同學(xué)看完都是懵懵的狀態(tài)，這得怎么統(tǒng)計(jì)呢?

關(guān)于什么是二叉搜索樹(shù)，我們之前在講解二叉樹(shù)專題的時(shí)候已經(jīng)詳細(xì)講解過(guò)了，也可以看看這篇二叉樹(shù)：二叉搜索樹(shù)登場(chǎng)!再回顧一波。

了解了二叉搜索樹(shù)之后，我們應(yīng)該先舉幾個(gè)例子，畫(huà)畫(huà)圖，看看有沒(méi)有什么規(guī)律，如圖：

不同的二叉搜索樹(shù)

n為1的時(shí)候有一棵樹(shù)，n為2有兩棵樹(shù)，這個(gè)是很直觀的。

不同的二叉搜索樹(shù)1

來(lái)看看n為3的時(shí)候，有哪幾種情況。

當(dāng)1為頭結(jié)點(diǎn)的時(shí)候，其右子樹(shù)有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和 n 為2的時(shí)候兩棵樹(shù)的布局是一樣的啊!

(可能有同學(xué)問(wèn)了，這布局不一樣啊，節(jié)點(diǎn)數(shù)值都不一樣。別忘了我們就是求不同樹(shù)的數(shù)量，并不用把搜索樹(shù)都列出來(lái)，所以不用關(guān)心其具體數(shù)值的差異)

當(dāng)3為頭結(jié)點(diǎn)的時(shí)候，其左子樹(shù)有兩個(gè)節(jié)點(diǎn)，看這兩個(gè)節(jié)點(diǎn)的布局，是不是和n為2的時(shí)候兩棵樹(shù)的布局也是一樣的啊!

當(dāng)2為頭結(jié)點(diǎn)的時(shí)候，其左右子樹(shù)都只有一個(gè)節(jié)點(diǎn)，布局是不是和n為1的時(shí)候只有一棵樹(shù)的布局也是一樣的啊!

發(fā)現(xiàn)到這里，其實(shí)我們就找到了重疊子問(wèn)題了，其實(shí)也就是發(fā)現(xiàn)可以通過(guò)dp[1] 和 dp[2] 來(lái)推導(dǎo)出來(lái)dp[3]的某種方式。

思考到這里，這道題目就有眉目了。

dp[3]，就是 元素1為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 + 元素2為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 + 元素3為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量

元素1為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有2個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有0個(gè)元素的搜索樹(shù)數(shù)量

元素2為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有1個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有1個(gè)元素的搜索樹(shù)數(shù)量

元素3為頭結(jié)點(diǎn)搜索樹(shù)的數(shù)量 = 右子樹(shù)有0個(gè)元素的搜索樹(shù)數(shù)量 * 左子樹(shù)有2個(gè)元素的搜索樹(shù)數(shù)量

有2個(gè)元素的搜索樹(shù)數(shù)量就是dp[2]。

有1個(gè)元素的搜索樹(shù)數(shù)量就是dp[1]。

有0個(gè)元素的搜索樹(shù)數(shù)量就是dp[0]。

所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]

如圖所示：

不同的二叉搜索樹(shù)2

此時(shí)我們已經(jīng)找到遞推關(guān)系了，那么可以用動(dòng)規(guī)五部曲再系統(tǒng)分析一遍。

1.確定dp數(shù)組(dp table)以及下標(biāo)的含義

dp[i] ：1到i為節(jié)點(diǎn)組成的二叉搜索樹(shù)的個(gè)數(shù)為dp[i]。

也可以理解是i的不同元素節(jié)點(diǎn)組成的二叉搜索樹(shù)的個(gè)數(shù)為dp[i] ，都是一樣的。

以下分析如果想不清楚，就來(lái)回想一下dp[i]的定義

2.確定遞推公式

在上面的分析中，其實(shí)已經(jīng)看出其遞推關(guān)系， dp[i] += dp[以j為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)數(shù)量]

j相當(dāng)于是頭結(jié)點(diǎn)的元素，從1遍歷到i為止。

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量，i-j 為以j為頭結(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)數(shù)量

3.dp數(shù)組如何初始化

初始化，只需要初始化dp[0]就可以了，推導(dǎo)的基礎(chǔ)，都是dp[0]。

那么dp[0]應(yīng)該是多少呢?

從定義上來(lái)講，空節(jié)點(diǎn)也是一棵二叉樹(shù)，也是一棵二叉搜索樹(shù)，這是可以說(shuō)得通的。

從遞歸公式上來(lái)講，dp[以j為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量] * dp[以j為頭結(jié)點(diǎn)右子樹(shù)節(jié)點(diǎn)數(shù)量] 中以j為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量為0，也需要dp[以j為頭結(jié)點(diǎn)左子樹(shù)節(jié)點(diǎn)數(shù)量] = 1， 否則乘法的結(jié)果就都變成0了。

所以初始化dp[0] = 1

4.確定遍歷順序

首先一定是遍歷節(jié)點(diǎn)數(shù)，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節(jié)點(diǎn)數(shù)為i的狀態(tài)是依靠 i之前節(jié)點(diǎn)數(shù)的狀態(tài)。

那么遍歷i里面每一個(gè)數(shù)作為頭結(jié)點(diǎn)的狀態(tài)，用j來(lái)遍歷。

代碼如下：

for (int i = 1; i <= n; i++) { 
    for (int j = 1; j <= i; j++) { 
        dp[i] += dp[j - 1] * dp[i - j]; 
    } 
} 

5.舉例推導(dǎo)dp數(shù)組

n為5時(shí)候的dp數(shù)組狀態(tài)如圖：

不同的二叉搜索樹(shù)3

當(dāng)然如果自己畫(huà)圖舉例的話，基本舉例到n為3就可以了，n為4的時(shí)候，畫(huà)圖已經(jīng)比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時(shí)候，把dp數(shù)組打出來(lái)，看看哪里有問(wèn)題。

綜上分析完畢，C++代碼如下：

class Solution { 
public: 
    int numTrees(int n) { 
        vector<int> dp(n + 1); 
        dp[0] = 1; 
        for (int i = 1; i <= n; i++) { 
            for (int j = 1; j <= i; j++) { 
                dp[i] += dp[j - 1] * dp[i - j]; 
            } 
        } 
        return dp[n]; 
    } 
}; 

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：

大家應(yīng)該發(fā)現(xiàn)了，我們分析了這么多，最后代碼卻如此簡(jiǎn)單!

總結(jié)

這道題目雖然在力扣上標(biāo)記是中等難度，但可以算是困難了!

首先這道題想到用動(dòng)規(guī)的方法來(lái)解決，就不太好想，需要舉例，畫(huà)圖，分析，才能找到遞推的關(guān)系。

然后難點(diǎn)就是確定遞推公式了，如果把遞推公式想清楚了，遍歷順序和初始化，就是自然而然的事情了。

可以看出我依然還是用動(dòng)規(guī)五部曲來(lái)進(jìn)行分析，會(huì)把題目的方方面面都覆蓋到!

而且具體這五部分析是我自己平時(shí)總結(jié)的經(jīng)驗(yàn)，找不出來(lái)第二個(gè)的，可能過(guò)一陣子 其他題解也會(huì)有動(dòng)規(guī)五部曲了，哈哈。

當(dāng)時(shí)我在用動(dòng)規(guī)五部曲講解斐波那契的時(shí)候，一些錄友和我反應(yīng)，感覺(jué)講復(fù)雜了。

其實(shí)當(dāng)時(shí)我一直強(qiáng)調(diào)簡(jiǎn)單題是用來(lái)練習(xí)方法論的，并不能因?yàn)楹?jiǎn)單我就代碼一甩，簡(jiǎn)單解釋一下就完事了。

可能當(dāng)時(shí)一些同學(xué)不理解，現(xiàn)在大家應(yīng)該感受方法論的重要性了，加油??

本文轉(zhuǎn)載自微信公眾號(hào)「代碼隨想錄」，可以通過(guò)以下二維碼關(guān)注。轉(zhuǎn)載本文請(qǐng)聯(lián)系代碼隨想錄公眾號(hào)。