這篇文章主要為大家展示了“LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題”，內(nèi)容簡(jiǎn)而易懂，條理清晰，希望能夠幫助大家解決疑惑，下面讓小編帶領(lǐng)大家一起研究并學(xué)習(xí)一下“LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題”這篇文章吧。

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供大安網(wǎng)站建設(shè)、大安做網(wǎng)站、大安網(wǎng)站設(shè)計(jì)、大安網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁(yè)設(shè)計(jì)與制作、大安企業(yè)網(wǎng)站模板建站服務(wù)，10多年大安做網(wǎng)站經(jīng)驗(yàn)，不只是建網(wǎng)站，更提供有價(jià)值的思路和整體網(wǎng)絡(luò)服務(wù)。

 

題目描述

給定一個(gè)整數(shù) n，求以 1 ... n 為節(jié)點(diǎn)組成的二叉搜索樹(shù)有多少種？

示例:

輸入: 3輸出: 5解釋:給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹(shù):
   1         3     3      2      1    \       /     /      / \      \     3     2     1      1   3      2    /     /       \                 \   2     1         2                 3

   

解題方案

 

思路

• 標(biāo)簽：動(dòng)態(tài)規(guī)劃

• 假設(shè)n個(gè)節(jié)點(diǎn)存在二叉排序樹(shù)的個(gè)數(shù)是G(n)，令f(i)為以i為根的二叉搜索樹(shù)的個(gè)數(shù)，則

• 當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹(shù)節(jié)點(diǎn)個(gè)數(shù)為i-1個(gè)，右子樹(shù)節(jié)點(diǎn)為n-i，則

• 綜合兩個(gè)公式可以得到卡特蘭數(shù)^[1]公式

 

 

代碼

class Solution {    public int numTrees(int n) {        int[] dp = new int[n+1];        dp[0] = 1;        dp[1] = 1;                for(int i = 2; i < n + 1; i++)            for(int j = 1; j < i + 1; j++)                 dp[i] += dp[j-1] * dp[i-j];                return dp[n];    }}

以上是“LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！