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

示例:

輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:

? ?1 ? ? ? ? 3 ? ? 3 ? ? ?2 ? ? ?1
? ? \ ? ? ? / ? ? / ? ? ?/ \ ? ? ?\
? ? ?3 ? ? 2 ? ? 1 ? ? ?1 ? 3 ? ? ?2
? ? / ? ? / ? ? ? \ ? ? ? ? ? ? ? ? \
? ?2 ? ? 1 ? ? ? ? 2 ? ? ? ? ? ? ? ? 3

思路：動態規劃，找到子問題關系為?G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

詳細講解參考鏈接

class Solution { public:int numTrees(int n) {vector<int> dp(n + 1, 0);dp[0] = 1;//利用G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)進行動態規劃for (int i = 1; i <= n; ++i){for (int j = 0; j < i; ++j){dp[i] += (dp[j] * dp[i - 1 - j]);}}return dp[n];} };

?

總結

以上是生活随笔為你收集整理的不同的二叉搜索树—leetcode96的全部內容，希望文章能夠幫你解決所遇到的問題。

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