溫馨提示×

您好，登錄后才能下訂單哦！

密碼登錄×
登錄注冊(cè)×
其他方式登錄
點(diǎn)擊 登錄注冊(cè) 即表示同意《億速云用戶服務(wù)條款》

LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題

發(fā)布時(shí)間：2021-12-15 09:20:11 來(lái)源：億速云 閱讀：125 作者：小新 欄目：大數(shù)據(jù)

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


 

題目描述

給定一個(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ù)，則

LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題

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

LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題

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

LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題

LeetCode如何解決不同的二叉搜索樹(shù)問(wèn)題  
算法動(dòng)圖
 

代碼

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)注億速云行業(yè)資訊頻道！

向AI問(wèn)一下細(xì)節(jié)

免責(zé)聲明：本站發(fā)布的內(nèi)容（圖片、視頻和文字）以原創(chuàng)、轉(zhuǎn)載和分享為主，文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱：is@yisu.com進(jìn)行舉報(bào)，并提供相關(guān)證據(jù)，一經(jīng)查實(shí)，將立刻刪除涉嫌侵權(quán)內(nèi)容。

AI
助
手