96不同的二叉搜索树

发表于 分类于
这是文章开头，显示在主页面，详情请点击此处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution:
    def numTrees(self, n: int) -> int:
        # 一道经典的动态规划题；
        # 直接根据题目问题定义 d[i] = i 个节点 对应的二叉搜索树种类数；
        # 任意个数的节点的总的二叉搜索树种树，总能以之前的节点数的二叉搜索树 推到而来；
        # 如果能够固定 根节点 ，那可能出现的二叉搜索树种类数量就有一个确定的关系：
        # 可能种数 = 左边节点数对应的种数 * 右边节点数对应的种数；

        # 由于搜索树的 左边一定比 根 小，右边一定比 根大，以三个节点为例子分析：分为三种情况
        # 情况一：1 为根；情况二：2为根；情况三：3为根；  
        # 情况一中，1 的左边是 0个节点，右边是2个节点；         种数 = d[0]*d[3-0-1=2]    
        # 情况二中：2 的左边是 1个节点，右边是 1 个节点；       种数 = d[1]*d[3-1-1=1]
        # 情况三中：3的左边是2个节点，右边是0 个节点；          种数 = d[2]*d[3-2-1=0]
        # 三种情况 求和才是 总的种类数；

        # 初始化： d[0] = 1 ; d[1] = 1; 但是 d的其他元素都要从0初始化，因为d涉及到累加求和；
        # 同时 d[1] = 1; 也不应该写出来，因为涉及到累加求和，d[1] 应该要推算出来才能保证结果正确；
        # 遍历顺序，考虑到递推公式是从小推大，所以从小遍历即可；
        d = [0 for _ in range(n+1)]
        d[0] = 1
        for i in range(1,n+1):        # 针对每一个i ，都有多种情况用 左边节点数 j 分开讨论汇总；
            for j in range(i):        # j 总是在 [0-i) 的左闭右开区间内；
                d[i] += d[j]*d[i-j-1]
            # print(d[i])     # 打印 检查;
        return d[n]