admin 管理员组

文章数量: 1087817

Python——动态规划法 求不同的二叉搜索树最多有多少

目录

    • 引言
    • 问题描述
    • 预期结果
    • 思路分析
    • 算法

引言

二叉搜索树又称二叉排序树，满足这样的条件：若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值。

问题描述

给定一个整数 n，求以 1，2，… n 为节点组成的二叉搜索树有多少种

预期结果

case 1: return 1;
case 2: return 2;
case 3: return 5;
case 4: return 14;
case 5: return 42;
case 6: return 132;
case 7: return 429;
case 8: return 1430;
case 9: return 4862;
case 10: return 16796;
case 11: return 58786;
case 12: return 208012;
case 13: return 742900;
case 14: return 2674440;
case 15: return 9694845;
case 16: return 35357670;
case 17: return 129644790;
case 18: return 477638700;
case 19: return 1767263190;

思路分析

假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则

G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n)

当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则

f(i) = G(i-1)*G(n-i)

综合两个公式可以得到 卡特兰数 公式

G(n) = G(0)*G(n-1)+G(1)*(n-2)+...+G(n-1)*G(0)

算法

class Solution:def numTrees(self, n):# 初始化大小为n+1的列表数组G = [0]*(n+1)G[0], G[1] = 1, 1# range是左闭右开for i in range(2, n+1):for j in range(1, i+1):G[i] += G[j-1] * G[i-j]return G[n]

本文标签： Python动态规划法 求不同的二叉搜索树最多有多少

版权声明：本文标题：Python——动态规划法 求不同的二叉搜索树最多有多少 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.roclinux.cn/p/1699082659a327115.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。