力扣-96.不同的二叉搜索树 题目详解
题目:
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
二叉搜索树介绍:
二叉搜索树是一个有序树：
-
若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；
-
若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；
-
它的左、右子树也分别为二叉搜索树
思路:
-
看题分析然后画图
当 n = 1时.
当 n = 2 时
当 n = 3 时
注意: 我们求的是不同树的数量,并不用把搜索树都列出来,所以不用关心具体数值的差异
-
接下来看看 n为3时 ,有哪几种情况:
1.当1为头节点:
其右子树有两个节点,其布局和 n=2 的布局一样
2.当3为头节点
其左子树有两个节点,其布局和 n=2 的布局一样
当2为头节点
其左右子树都只有一个节点,其布局和 n=1 的布局一样
经过上面分析,我们找到了重叠子问题了,发现可以通过dp[1]和dp[2]可以推导出dp[3]的某种方式
-
思考以上得出:
dp[3]计算过程:
dp[3]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量 + 元素3为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有2个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有1个元素的搜索树数量
元素3为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有2个元素的搜索树数量
有2个元素的搜索树数量就是dp[2]。
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[3] = dp[2] * dp[0] + dp[1] * dp[1] + dp[0] * dp[2]
dp[2]计算过程:
dp[2]，就是 元素1为头结点搜索树的数量 + 元素2为头结点搜索树的数量
元素1为头结点搜索树的数量 = 右子树有1个元素的搜索树数量 * 左子树有0个元素的搜索树数量
元素2为头结点搜索树的数量 = 右子树有0个元素的搜索树数量 * 左子树有1个元素的搜索树数量
有1个元素的搜索树数量就是dp[1]。
有0个元素的搜索树数量就是dp[0]。
所以dp[2] = dp[0] * dp[1] + dp[1] * dp[0]
如图所示:
动规五部曲系统分析:
已经找到了递推关系,接下来用动规五部曲在系统分析一遍
-
确定dp数组的下标以及含义:
dp[i]: 1到i为节点组成的二叉搜索树的个数为dp[i]
也可以理解为:i个不同元素节点组成的二叉搜索树的个数
-
定递推关系式:
dp[i] +=dp[以j为头节点左子树节点数量] * dp[以j为头节点右子树节点数量]
其中j相当于是头节点的元素,从1遍历到i为止
递推公式:dp[i] +=dp[j - 1] * dp[i - j]
j - 1为: 以j为头节点左子树节点数量
i - j 为: 以j为头节点右子树节点数量
i - j 表示的是右子树的节点数。在这个问题中，我们遍历每个数字 i 作为根节点，然后遍历所有可能的左子树节点数 j-1。由于根节点 i 已经被选定，所以右子树的节点数就是 i 减去左子树的节点数 j，即 i - j。 例如，假设我们有 i = 5 个节点，我们尝试将数字 3 作为根节点。此时，左子树的节点数为 j-1 = 2，右子树的节点数就是 i - j = 5 - 3 = 2。我们需要计算左子树和右子树的所有可能组合，即 dp[j - 1] * dp[i - j]，然后将这些组合累加到 dp[i] 中。
-
dp数组初始化:
只要初始dp[0]就可以了
从递归公式上看, dp[以j为头节点左子树节点数量] * dp[以j为头节点右子树节点数量] 中以j为头结点左子树节点数量为0，也需要dp[以j为头结点左子树节点数量] = 1， 否则乘法的结果就都变成0了。
-
确定遍历顺序
首先遍历节点数,从递归公式: dp[i] += dp[j-1] * dp[i-j] 可以看出, 节点数为i的状态是依靠之前节点数的状态
遍历 i 里面每一个数作为头节点的状态,用 j 来遍历
for i in range(1, n+1)
for j in range(1, i+1)
dp[i] += dp[j - 1] * dp[i - j]
-
列举推导dp数组
当n=5时,dp数组状态如图
完整代码:
def numTrees(n):
"""
自定义函数,计算给定节点数n的不同二叉搜索树的数量
:param n: 二叉搜索树的节点数
:return: 不同的二叉搜索树的数量
"""
# 如果节点数为1或0, 那么只有一种情况,即空树或者只有一个节点的数
if n==0 or n==1:
return 1
# 初始化动态规划数组，长度为n+1，因为包括0个节点的情况
dp = [0] * (n + 1)
# 0个节点的二叉搜索树只有1种，即空树
dp[0] = 1
# 遍历每个节点数，从1到n
for i in range(1, n + 1):
# 对于每个数字i, 计算以i为根节点的二叉搜索树的数量
for j in range(1, i + 1):
# 左子树的节点数为j-1，右子树的节点数为i-j
# 左子树的不同二叉搜索树数量乘以右子树的不同二叉搜索树数量
# 就是以j为根节点的不同二叉搜索树的数量
dp[i] += dp[j - 1] * dp[i - j]
# 返回n个节点的不同二叉搜索树的数量
return dp[n]
if __name__ == '__main__':
# 测试函数，输出4个节点的不同二叉搜索树的数量
print(numTrees(1))