python二叉搜索树实例分析
本文小编为大家详细介绍“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二叉搜索树实例分析”文章已经介绍完毕，想要掌握这篇文章的知识点还需要大家自己动手实践使用过才能领会，如果想了解更多相关内容的文章，欢迎关注创新互联行业资讯频道。
分享名称：python二叉搜索树实例分析
标题网址：http://myzitong.com/article/gjjgpj.html