Leetcode 96. 不同的二叉搜索樹

96. 不同的二叉搜索樹

給你一個整數 n ，求恰由 n 個節點組成且節點值從 1 到 n 互不相同的 二叉搜索樹 有多少種？返回滿足題意的二叉搜索樹的種數。
示例 1：

輸入：n = 3
輸出：5

示例 2：

輸入：n = 1
輸出：1

提示：

1 <= n <= 19

思路

我們可以把n = 1 2 3 這三種情况都列出來，然後我們可以發現：
n = 1時，只有一個結點，值為1，也只能組成一種二叉搜索樹。
n = 2時，1 2 可以1 為節點，也可以2為根節點，所以是兩種情况。
n = 3時，也就是上圖中的這一種情况，共五種情况，可以分成三大類：

1. 1為根節點：剩下的都比1大，所以左子樹有 1 - 1 = 0個結點，右子樹有3 - 1 = 2個結點，那麼情况又變成了右子樹兩個結點，左子樹零個結點。所以此時次數 = 左子樹0個結點的種類數 * 右子樹2個結點的種類數
2. 2為根節點：左子樹 2 - 1 = 1個結點，右子樹 3 - 2 = 1個結點，所以此時次數 = 左子樹一個結點 * 右子樹一個結點
3. 3為根節點：左子樹 3 - 1 = 2個結點，右子樹 3 - 3 = 0個結點，所以此時次數 = 左子樹兩個結點 * 右子樹一個結點

而我們也可以知道，無論左子樹還是右子樹對應結點數的種類數就等於dp[i]的值。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2];
對於第 i 個結點，要考慮從 1 到 i 作為根節點的情况，所以需要累加
一共是 i 個結點，對於根節點 j ，此時，左子樹有 j - 1 個結點，右子樹有 i - j 個結點

代碼

class Solution {
    
public:
    int numTrees(int n) {
    
        int dp[n + 1];
        for (int i = 0; i <= n; i++) dp[i] = 0;
        dp[0] = 1;

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

        return dp[n];
    }
};
/* //對於第i個節點，需要考慮1作為根節點直到i作為根節點的情况，所以需要累加 //一共i個節點，對於根節點j時,左子樹的節點個數為j-1，右子樹的節點個數為i-j */

/* 元素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] */