[数据结构与算法]96. 不同的二叉搜索树

96. 不同的二叉搜索树

原始题目链接：https://leetcode-cn.com/problems/unique-binary-search-trees/

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

解题思路：

题目求解不同的二叉搜索树的个数，这种求不同的个数或不同走法等类似的问题，可以想到可能是要用动态规划的方法解题。动态规划三步走：定义状态，找状态转移方程，边界赋初始值。具体实现看代码及注释。

代码实现：

class Solution:
    def numTrees(self, n: int) -> int:
        # 定义状态：
        # T(n) 表示长度为n的序列构成不同二叉搜索树的个数
        # C(i，n) 表示以i为根序列长度为n的不同二叉搜索树的个数（1<=i<=n）
        # C(i，n) 拆解，就是i的左子序列构成的不同二叉树的个数 + 右子序列构成的不同的二叉树的个数
        # 所以状态转移方程：
        # T(n) = 对 C(i, n)遍历i从1到n的加和，T(n) = T(i - 1) + T(n - i)的对i求加和
        # 边界：
        # n=0 n=1的时候，不同二叉树的个数是1，空二叉树也算一种

        # 申请一个数组，存放节点为n时的不同二叉搜索数的个数
        T = [0] * (n + 1)

        T[0], T[1] = 1, 1

        # 遍历n个节点，从n=2开始
        for i in range(2, n + 1):
            # i个节点中当j为根的时候，j可以从这个i个节点中取值，计算T(i)
            for j in range(1, i + 1):
                # 计算当前一共为i个节点的所有不同二叉搜索树的个数，根据上面的分析是求加和
                T[i] += T[j - 1] * T[i - j]
        
        # 最后数组的元素就是序列长度为n构成的不同二叉搜索树的个数
        return T[-1]

参考文献：
https://leetcode-cn.com/problems/unique-binary-search-trees/solution/bu-tong-de-er-cha-sou-suo-shu-by-leetcode-solution/