算法题--包含1~n的所有二叉搜索树的个数

image.png

0. 链接

题目链接

1. 题目

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

2. 思路2: 动态规划

• 观察到一个事实, [1 2]的可列树结构, 与[99,100]的可列树结构之间, 具有结构相同的特性，只是数值上相差一个98
• 利用这个事实, 可以大量复用长度相同的连续数字构成的子树计算结果
• 具体来讲

dp[0] = 1

for i in range(1, n + 1):
    dp[n] += dp[i - 1] * dp[n - i]

解释:

• 子树的个数只跟节点数有关, 所以可以使用dp[i]来记录节点数为i的可能子树数
• 对于某个节点数n, 根节点i可以取1~n,
• 对于每一个确定的根节点i, 左右子树的节点数分别为i-1和n-i， 这样两个树的选择数就是dp[i - 1]和dp[n - i]的乘积
• 将这些乘积都累加起来, 就得到节点数n对应的独立搜索树个数
• 为了在计算n的时候用到的dp[i - 1]和dp[n - i]都已计算好, 可以让节点数从1~n逐渐计算, 这样前面计算出的结果, 就可以被后面的n来使用, 可以节省计算量

3. 代码

# coding:utf8
class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left = None
        self.right = None


class Solution:
    def numTrees(self, n: int) -> int:
        dp = [None] * (n + 1)
        dp[0] = 0
        if n == 0:
            return dp[0]

        dp[0] = 1
        for num in range(1, n + 1):
            dp[num] = 0
            for i in range(1, num + 1):
                dp[num] += dp[i - 1] * dp[num - i]

        return dp[n]


def my_test(solution, n):
    print('input: n={}, output: {}'.format(n, solution.numTrees(n)))


solution = Solution()
my_test(solution, 0)
my_test(solution, 1)
my_test(solution, 2)
my_test(solution, 3)
my_test(solution, 4)

输出结果

input: n=0, output: 0
input: n=1, output: 1
input: n=2, output: 2
input: n=3, output: 5
input: n=4, output: 14

结果

image.png