不同的二叉搜索樹

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

給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種?

示例:

思路

這道題目描述很簡短，但估計大部分同學看完都是懵懵的狀態，這得怎么統計呢?

關于什么是二叉搜索樹，我們之前在講解二叉樹專題的時候已經詳細講解過了，也可以看看這篇二叉樹：二叉搜索樹登場!再回顧一波。

了解了二叉搜索樹之后，我們應該先舉幾個例子，畫畫圖，看看有沒有什么規律，如圖：

不同的二叉搜索樹

n為1的時候有一棵樹，n為2有兩棵樹，這個是很直觀的。

不同的二叉搜索樹1

來看看n為3的時候，有哪幾種情況。

當1為頭結點的時候，其右子樹有兩個節點，看這兩個節點的布局，是不是和 n 為2的時候兩棵樹的布局是一樣的啊!

(可能有同學問了，這布局不一樣啊，節點數值都不一樣。別忘了我們就是求不同樹的數量，并不用把搜索樹都列出來，所以不用關心其具體數值的差異)

當3為頭結點的時候，其左子樹有兩個節點，看這兩個節點的布局，是不是和n為2的時候兩棵樹的布局也是一樣的啊!

當2為頭結點的時候，其左右子樹都只有一個節點，布局是不是和n為1的時候只有一棵樹的布局也是一樣的啊!

發現到這里，其實我們就找到了重疊子問題了，其實也就是發現可以通過dp[1] 和 dp[2] 來推導出來dp[3]的某種方式。

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

dp[3]，就是 元素1為頭結點搜索樹的數量 + 元素2為頭結點搜索樹的數量 + 元素3為頭結點搜索樹的數量

元素1為頭結點搜索樹的數量 = 右子樹有2個元素的搜索樹數量 * 左子樹有0個元素的搜索樹數量

元素2為頭結點搜索樹的數量 = 右子樹有1個元素的搜索樹數量 * 左子樹有1個元素的搜索樹數量

元素3為頭結點搜索樹的數量 = 右子樹有0個元素的搜索樹數量 * 左子樹有2個元素的搜索樹數量

有2個元素的搜索樹數量就是dp[2]。

有1個元素的搜索樹數量就是dp[1]。

有0個元素的搜索樹數量就是dp[0]。

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

如圖所示：

不同的二叉搜索樹2

此時我們已經找到遞推關系了，那么可以用動規五部曲再系統分析一遍。

1.確定dp數組(dp table)以及下標的含義

dp[i] ：1到i為節點組成的二叉搜索樹的個數為dp[i]。

也可以理解是i的不同元素節點組成的二叉搜索樹的個數為dp[i] ，都是一樣的。

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

2.確定遞推公式

在上面的分析中，其實已經看出其遞推關系， dp[i] += dp[以j為頭結點左子樹節點數量] * dp[以j為頭結點右子樹節點數量]

j相當于是頭結點的元素，從1遍歷到i為止。

所以遞推公式：dp[i] += dp[j - 1] * dp[i - j]; ，j-1 為j為頭結點左子樹節點數量，i-j 為以j為頭結點右子樹節點數量

3.dp數組如何初始化

初始化，只需要初始化dp[0]就可以了，推導的基礎，都是dp[0]。

那么dp[0]應該是多少呢?

從定義上來講，空節點也是一棵二叉樹，也是一棵二叉搜索樹，這是可以說得通的。

從遞歸公式上來講，dp[以j為頭結點左子樹節點數量] * dp[以j為頭結點右子樹節點數量] 中以j為頭結點左子樹節點數量為0，也需要dp[以j為頭結點左子樹節點數量] = 1， 否則乘法的結果就都變成0了。

所以初始化dp[0] = 1

4.確定遍歷順序

首先一定是遍歷節點數，從遞歸公式：dp[i] += dp[j - 1] * dp[i - j]可以看出，節點數為i的狀態是依靠 i之前節點數的狀態。

那么遍歷i里面每一個數作為頭結點的狀態，用j來遍歷。

代碼如下：

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

5.舉例推導dp數組

n為5時候的dp數組狀態如圖：

不同的二叉搜索樹3

當然如果自己畫圖舉例的話，基本舉例到n為3就可以了，n為4的時候，畫圖已經比較麻煩了。

我這里列到了n為5的情況，是為了方便大家 debug代碼的時候，把dp數組打出來，看看哪里有問題。

綜上分析完畢，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]; 
    } 
}; 

• 時間復雜度：
• 空間復雜度：

大家應該發現了，我們分析了這么多，最后代碼卻如此簡單!

總結

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

首先這道題想到用動規的方法來解決，就不太好想，需要舉例，畫圖，分析，才能找到遞推的關系。

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

可以看出我依然還是用動規五部曲來進行分析，會把題目的方方面面都覆蓋到!

而且具體這五部分析是我自己平時總結的經驗，找不出來第二個的，可能過一陣子 其他題解也會有動規五部曲了，哈哈。

當時我在用動規五部曲講解斐波那契的時候，一些錄友和我反應，感覺講復雜了。

其實當時我一直強調簡單題是用來練習方法論的，并不能因為簡單我就代碼一甩，簡單解釋一下就完事了。

可能當時一些同學不理解，現在大家應該感受方法論的重要性了，加油??

本文轉載自微信公眾號「代碼隨想錄」，可以通過以下二維碼關注。轉載本文請聯系代碼隨想錄公眾號。