不同的二叉搜索树

Leetcode Link: 96. 不同的二叉搜索树 - 力扣（LeetCode）

题目

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

解法一

思路：本题要是上来就干，很麻烦，我干了好几次没干过去，要仔细动脑

先理解严格二叉搜索树的一个重要知识：无重复数字

故，本题总结成一句话：二叉搜索树的数量和数字的值无关，只和数字的个数有关。

举个例子，譬如 [1,2,3] 组成的二叉搜索树的数量是不是和 [4,7,14] 组成的数量一样？

理解了上面，我们下面拆解问题。 一般情况，比如给了五个数字，大小排好序为 [a,b,c,d,e]

• 用 a 当根节点，那么 b, c, d, e 只能是右子树，左子树为空，此情况下构成的二叉搜索树的数量=4 个数字构成的二叉搜索树数量，记为 $n(0)\times n(4)$
• 当 b 为根节点，那么 a 只能是左子树，c, d, e 只能构成右子树。此情况下数量=左子树数量*右子树数量= $n(1)\times n(3)$
• 当 c 为根节点，那么 a, b 只能是左子树，d, e 只能构成右子树。此情况下数量=左子树数量*右子树数量= $n(2)\times n(2)$
• 当 d 为根节点，那么 a, b, c 只能是左子树，e 只能构成右子树。此情况下数量=左子树数量*右子树数量= $n(3)\times n(1)$
• 当 d 为根节点，那么 a,b,c,d 只能是左子树，没有右子树。此情况下数量=左子树数量*右子树数量= $n(4)\times n(0)$

我们考虑 $n(0)$ 应该为多少。 显然，只能构成一个空二叉搜索树，因此 $n(0)=1$ 同理，$n(1)=1$

通过以上的分析，可以用动态规划去做。

题解：

class Solution:
    def numTrees(self, n: int) -> int:
        if n == 1:
            return 1
        dp = [1] * (n+1)  # dp[0]==1 用来方便后面编程
        dp[1] = 1
        dp[2] = 2
        for i in range(2, len(dp)):
            tmp = 0
            for j in range(i):# 单边子树最多有i-1个元素，因此j最大取到i-1
                tmp = tmp + dp[j]*dp[i-1-j] # [i-1-j]先减去了被选择做根节点的元素，开始就忘了。
            dp[i] = tmp
        
        return dp[n]

启发和联系