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

創(chuàng)新互聯(lián)公司專業(yè)為企業(yè)提供大安網(wǎng)站建設(shè)、大安做網(wǎng)站、大安網(wǎng)站設(shè)計(jì)、大安網(wǎng)站制作等企業(yè)網(wǎng)站建設(shè)、網(wǎng)頁設(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)組成的二叉搜索樹有多少種？

示例:

輸入: 3輸出: 5解釋:給定 n = 3, 一共有 5 種不同結(jié)構(gòu)的二叉搜索樹:
   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)存在二叉排序樹的個(gè)數(shù)是G(n)，令f(i)為以i為根的二叉搜索樹的個(gè)數(shù)，則

• 當(dāng)i為根節(jié)點(diǎn)時(shí)，其左子樹節(jié)點(diǎn)個(gè)數(shù)為i-1個(gè)，右子樹節(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如何解決不同的二叉搜索樹問題”這篇文章的所有內(nèi)容，感謝各位的閱讀！相信大家都有了一定的了解，希望分享的內(nèi)容對(duì)大家有所幫助，如果還想學(xué)習(xí)更多知識(shí)，歡迎關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道！

網(wǎng)站名稱：LeetCode如何解決不同的二叉搜索樹問題
本文來源：http://jinyejixie.com/article48/pgepep.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站排名、響應(yīng)式網(wǎng)站、網(wǎng)站內(nèi)鏈、云服務(wù)器、品牌網(wǎng)站制作、移動(dòng)網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)