專欄：50多種數據結構徹底征服

專欄：50多種經典圖論算法全部掌握

最近一網友在網上發文稱pdd的校招禮物是2025春節祝福表情包，該網友繃不住了，還引起其他網友的熱議，有的網友稱之前還發了電子臺歷，還有的發了校招壁紙。我離校招都十多年了，不記得當時是否有校招禮物，現在都流行發這個嗎？

--------------下面是今天的算法題--------------

來看下今天的算法題，這題是LeetCode的第96題：不同的二叉搜索樹。

問題描述

來源：LeetCode第96題

難度：中等

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

示例1：

輸入：n = 3 輸出：5

示例2：

輸入：n = 1 輸出：1

• 1 <= n <= 19

問題分析

這題讓計算 n 個節點可以構成多個二叉搜索樹。我們可以這樣來思考，二叉樹肯定有根節點，去掉根節點之后還有 n-1 個子節點。在這 n-1 個子節點中，左子節點可以有 0 個，也可以有 1 個，也可以有 2 個……

如果左子節點是 j 個，那么右子節點就是 n-1-j 個，它們構成的二叉搜索樹就是左子樹構成的個數乘以右子樹構成的個數，所以這是一個動態規劃問題。

定義dp[i]表示 i 個節點構成的二叉搜索樹個數，當 i 等于 1 的時候只有一種情況。當左子節點個數為 0 的時候，構成的二叉搜索樹就是右子節點構成的個數，所以我們這里讓dp[0]也等于 1 。

當計算 i 個節點的時候，我們只需要枚舉左子樹的個數從 0 到 i-1 即可，代碼如下：

JAVA：

public int numTrees(int n) {     int dp[] = new int[n + 1];     dp[0] = dp[1] = 1;// 節點為0和1的時候，只有一種。     for (int i = 2; i <= n; i++)         for (int j = 0; j < i; j++)             // j是左子節點個數，i-j-1是右子節點個數。             dp[i] += dp[j] * dp[i - j - 1];     return dp[n]; }

C++：

public:     int numTrees(int n) {         vector

  dp(n + 1);         dp[0] = dp[1] = 1;// 節點為0和1的時候，只有一種。         for (int i = 2; i <= n; i++)             for (int j = 0; j < i; j++)                 // j是左子節點個數，i-j-1是右子節點個數。                 dp[i] += dp[j] * dp[i - j - 1];         return dp[n];     }

Python：

def numTrees(self, n: int) -> int:     dp = [0] * (n + 1)     dp[0] = dp[1] = 1  # 節點為0和1的時候，只有一種。     for i in range(2, n + 1):         for j in range(i):             # j是左子節點個數，i-j-1是右子節點個數。             dp[i] += dp[j] * dp[i - j - 1]     return dp[n]

筆者簡介

博哥，真名：王一博，畢業十多年， 作者，專注于 數據結構和算法 的講解，在全球30多個算法網站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以 下載我整理的1000多頁的PDF算法文檔 。