解題思路：

因為二叉搜索樹的左右子樹均為二叉搜索樹。輸入整數n，求其所有二叉搜索樹的總數，就是求根節點分別為1,2, ..., n的二叉搜索樹的總和。

假設 i 的二叉搜索樹的總數為 f(i)，當根節點為 j 時，其二叉搜索樹的總數為其左子樹總數乘以右子樹總數，即 f(j - 1) * f(n - j)。

所以我們只要記錄一個數組nums就可以了。

?

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

?

?

總結

以上是生活随笔為你收集整理的Leetcode 96. 不同的二叉搜索树 解题思路及C++实现的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。