溫馨提示×

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

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

python二叉搜索樹實(shí)例分析

發(fā)布時(shí)間：2022-03-22 16:25:20 來源：億速云 閱讀：287 作者：iii 欄目：大數(shù)據(jù)

本文小編為大家詳細(xì)介紹“python二叉搜索樹實(shí)例分析”，內(nèi)容詳細(xì)，步驟清晰，細(xì)節(jié)處理妥當(dāng)，希望這篇“python二叉搜索樹實(shí)例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學(xué)習(xí)新知識(shí)吧。

【題目】

給定一個(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

【思路】

對(duì)于n個(gè)節(jié)點(diǎn)的樹，除了根節(jié)點(diǎn)外，節(jié)點(diǎn)在左子樹和右子樹上的數(shù)目分布可能是左0右n-1，左1右n-2，...，左n-2右1，左n-1右0。

用公式表示：dp[n] = dp[0] * dp[n - 1] + dp[1] * dp[n - 2] + ··· + dp[n - 2] * dp[1] + dp[n - 1] * dp[0]

【代碼】

python版本

class Solution:
    def numTrees(self, n: int) -> int:
        if n < 2:
            return n
        
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1
        # dp[i] = dp[0] * dp[i - 1] + dp[1] * dp[i - 2] + ... + dp[i - 1] * dp[0]
        for i in range(2, n + 1):
            for j in range(i):
                dp[i] += dp[j] * dp[i - j - 1]
        print(dp)
        return dp[-1]

讀到這里，這篇“python二叉搜索樹實(shí)例分析”文章已經(jīng)介紹完畢，想要掌握這篇文章的知識(shí)點(diǎn)還需要大家自己動(dòng)手實(shí)踐使用過才能領(lǐng)會(huì)，如果想了解更多相關(guān)內(nèi)容的文章，歡迎關(guān)注億速云行業(yè)資訊頻道。

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

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

AI
助
手