一:題目

二：上碼

class Solution { public:/**思路:1.分析題意二叉搜索樹(左子樹結(jié)點(diǎn)小于根節(jié)點(diǎn) 根節(jié)點(diǎn)小于右節(jié)點(diǎn))n=1時(shí)有一種形態(tài),n=0的話，空樹也是一種形態(tài)當(dāng)n=2的時(shí)候，二叉樹有兩種形狀當(dāng) n = 3的時(shí)候跟結(jié)點(diǎn)可以是1，2，3根節(jié)點(diǎn)為1的時(shí)候，其右子樹有兩個(gè)結(jié)點(diǎn),那么其有兩種形態(tài)和n=2的形態(tài)相同根節(jié)點(diǎn)為3的時(shí)候和根節(jié)點(diǎn)為1的情況類似則dp[3] = 根節(jié)點(diǎn)為1的時(shí)候的形狀數(shù)目+根節(jié)點(diǎn)為2的形狀數(shù)+根節(jié)點(diǎn)為3的形狀數(shù)目 2.動(dòng)態(tài)規(guī)劃5不步走1>:確定dp數(shù)組的含義和下標(biāo)的含義dp[i]表示的是 n為i的時(shí)候的形狀數(shù) 2>:確定dp數(shù)組的狀態(tài)遞推公式dp[i] = dp[以j頭結(jié)點(diǎn)的左子樹結(jié)點(diǎn)個(gè)數(shù)] * dp[以j為頭結(jié)點(diǎn)的右子樹的結(jié)點(diǎn)個(gè)數(shù)] 因?yàn)橐灶^結(jié)點(diǎn)是[0,n]，所以：dp[i] += dp[j-1] * dp[i-j];這里的j-1代表是比j小的個(gè)數(shù)有j-1個(gè)（左子樹嘛就是結(jié)點(diǎn)的值比根節(jié)點(diǎn)小）i-j代表的是比j大的有i-j個(gè)（同理）3>:確定dp數(shù)組的如何初始化dp[0] = 1,空樹也是 一種形態(tài)4>:確定dp數(shù)組的遍歷順序從前向后遍歷5>:舉例驗(yàn)證*/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++) {//以j為頭節(jié)點(diǎn)的話,dp[i] += dp[j-1] * dp[i-j];//dp[j-1]:以j為頭節(jié)點(diǎn)左子樹結(jié)點(diǎn)個(gè)數(shù);dp[i-j]:以j為頭結(jié)點(diǎn)右子樹的個(gè)數(shù)}}return dp[n];} };

安！

總結(jié)

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

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。