当前位置: 首页 > news >正文

力扣-96.不同的二叉搜索树 题目详解

题目:

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

二叉搜索树介绍:

二叉搜索树是一个有序树:

  • 若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值;

  • 若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值;

  • 它的左、右子树也分别为二叉搜索树

思路:

  1. 看题分析然后画图

当 n = 1时.

当 n = 2 时

当 n = 3 时

注意: 我们求的是不同树的数量,并不用把搜索树都列出来,所以不用关心具体数值的差异

  1. 接下来看看 n为3时 ,有哪几种情况:

1.当1为头节点:

其右子树有两个节点,其布局和 n=2 的布局一样

2.当3为头节点

其左子树有两个节点,其布局和 n=2 的布局一样

当2为头节点

其左右子树都只有一个节点,其布局和 n=1 的布局一样

经过上面分析,我们找到了重叠子问题了,发现可以通过dp[1]和dp[2]可以推导出dp[3]的某种方式

  1. 思考以上得出:

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]

如图所示:

动规五部曲系统分析:

已经找到了递推关系,接下来用动规五部曲在系统分析一遍

  1. 确定dp数组的下标以及含义:

dp[i]: 1到i为节点组成的二叉搜索树的个数为dp[i]

也可以理解为:i个不同元素节点组成的二叉搜索树的个数

  1. 定递推关系式:

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] 中。

  1. dp数组初始化:

只要初始dp[0]就可以了

从递归公式上看, dp[以j为头节点左子树节点数量] * dp[以j为头节点右子树节点数量] 中以j为头结点左子树节点数量为0,也需要dp[以j为头结点左子树节点数量] = 1, 否则乘法的结果就都变成0了。

  1. 确定遍历顺序

首先遍历节点数,从递归公式: 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]

  1. 列举推导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到nfor 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))
​


http://www.mrgr.cn/news/27647.html

相关文章:

  • vmware集群 vSAN HCL 数据库
  • 安全见闻1-5
  • 量子计算与人工智能的交汇:科技未来的新引擎
  • 【AI大模型】大型语言模型LLM基础概览:技术原理、发展历程与未来展望
  • Bottom-Up Attention(借助CNN)
  • 【Framework系列】UnityEditor调用外部程序详解
  • SBAS星基增强系统基础介绍
  • SEGGERS实时系统embOS推出Linux端模拟器
  • GEE 教程:利用Google Dynamic数据进行逐月指定区域的土地分类数据提取分析
  • 开发指南061-nexus权限管理
  • [网络]https的概念及加密过程
  • 基于Spring搭建SpringMvc框架
  • 从ANN到SNN的转换:实现、原理及两种归一化方法【MINIST、实战】
  • ICPC网络赛 以及ACM训练总结
  • 电脑上如何多开微信软件(多个微信同时使用)
  • 【AI学习】了解OpenAI o1背后的self-play RL:开启新的智能道路
  • vue中提示Parsing error: No Babel config file detected
  • Delta Lake
  • 基于SSM+Vue+MySQL的新生报到管理系统
  • 证券api接口,一个开源Python量化交易平台项目需要考虑哪些方面
  • CSP-CCF★★★201903-2二十四点★★★
  • 基于Python实现一个庆祝国庆节的小程序
  • 国内人工智能产业发展现状及对策研究
  • 人工智能——猴子摘香蕉问题
  • 拓扑排序算法
  • 深入理解Java中的偏向锁、轻量级锁与重量级锁