溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文小編為大家詳細介紹“python二叉搜索樹實例分析”，內容詳細，步驟清晰，細節處理妥當，希望這篇“python二叉搜索樹實例分析”文章能幫助大家解決疑惑，下面跟著小編的思路慢慢深入，一起來學習新知識吧。
【題目】
給定一個整數 n，求以 1 ... n 為節點組成的二叉搜索樹有多少種？
示例:
輸入: 3
輸出: 5
解釋:
給定 n = 3, 一共有 5 種不同結構的二叉搜索樹:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3【思路】
對于n個節點的樹，除了根節點外，節點在左子樹和右子樹上的數目分布可能是左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二叉搜索樹實例分析”文章已經介紹完畢，想要掌握這篇文章的知識點還需要大家自己動手實踐使用過才能領會，如果想了解更多相關內容的文章，歡迎關注億速云行業資訊頻道。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
