96.不同的二叉搜索树


  题目:

96. 不同的二叉搜索树

中等

2.4K

相关企业

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

示例 1:

输入:n = 3
输出:5

示例 2:

输入:n = 1
输出:1

提示:

  • 1 <= n <= 19

思考历程与知识点: 

来看看n为3的时候,有哪几种情况。

当1为头结点的时候,其右子树有两个节点,和 n 为2的时候两棵树的布局是一样的!

(可能有同学问了,这布局不一样啊,节点数值都不一样。别忘了我们就是求不同树的数量,并不用把搜索树都列出来,所以不用关心其具体数值的差异)

当3为头结点的时候,其左子树有两个节点,看这两个节点的布局,是不是和n为2的时候两棵树的布局也是一样的啊!

当2为头结点的时候,其左右子树都只有一个节点,布局是不是和n为1的时候只有一棵树的布局也是一样的啊!

发现到这里,其实我们就找到了重叠子问题了,其实也就是发现可以通过dp[1] 和 dp[2] 来推导出来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数组(dp table)以及下标的含义

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

也可以理解是i个不同元素节点组成的二叉搜索树的个数为dp[i] ,都是一样的。

以下分析如果想不清楚,就来回想一下dp[i]的定义

  • 确定递推公式

在上面的分析中,其实已经看出其递推关系, dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

j相当于是头结点的元素,从1遍历到i为止。

所以递推公式:dp[i] += dp[j - 1] * dp[i - j]; ,j-1 为j为头结点左子树节点数量,i-j 为以j为头结点右子树节点数量

  • dp数组如何初始化

初始化,只需要初始化dp[0]就可以了,推导的基础,都是dp[0]。

那么dp[0]应该是多少呢?

从定义上来讲,空节点也是一棵二叉树,也是一棵二叉搜索树,这是可以说得通的。

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

所以初始化dp[0] = 1

  • 确定遍历顺序

首先一定是遍历节点数,从递归公式:dp[i] += dp[j - 1] * dp[i - j]可以看出,节点数为i的状态是依靠 i之前节点数的状态。

那么遍历i里面每一个数作为头结点的状态,用j来遍历。

代码如下:

for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}
}

 题解:

class Solution {
public:int numTrees(int n) {vector<int> dp(n + 1);dp[0] = 1;for (int i = 1; i <= n; i++) {for (int j = 1; j <= i; j++) {dp[i] += dp[j - 1] * dp[i - j];}}return dp[n];}
};

欢迎点赞,收藏,评论,你的鼓励就是我创作的最大动力!(๑╹◡╹)ノ"""

版权声明:本文为CSDN博主「渡梦酒」的原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接及本声明。
原文链接:渡梦酒的博客_CSDN博客-csdn领域博主

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/141199.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

数据结构-----树和二叉树必知必会知识

目录 前言 思维导图 一.树 树的定义 二.二叉树 1.二叉树的定义 2.二叉树的形态&#xff08;图&#xff09; 3.二叉树的性质 三.满二叉树 1.定义 2.特点和性质 四.完全二叉树 1.定义 2.特点和性质 前言 今天开始我们就学习新的数据结构类型啦&#xff01;没错它就是…

python安全工具开发笔记(四)——python网络编程

一、C/S架构 什么是C/S架构 C : Client S : Server。客户机和服务器结构。 Server 唯一的目的就是等待Client 的请求&#xff0c;Client 连上 Server 发送必要的数据&#xff0c;然后等待Server端完成请求的反馈。 C/S网络编程 Server端进行设置&#xff0c;首先创建一个通信…

【LeetCode75】第六十三题 不同路径

目录 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 代码&#xff1a; 题目&#xff1a; 示例&#xff1a; 分析&#xff1a; 题目给我们返回地图的长和宽。问我们从地图的左上走到右下有几种方法。我们只能往下走或是往右走。 这个算是简单的二维动态规划题了。 …

RabbitMQ生产故障问题分析

1. 问题引发 由某个服务BI-collector-xx队列出现阻塞&#xff0c;影响很整个rabbitMQ集群服务不可用&#xff0c;多个应用MQ生产者服务出现假死状态&#xff0c;系统影响面较广&#xff0c;业务影响很大。当时为了应急处理&#xff0c;恢复系统可用&#xff0c;运维相对粗暴的把…

华为OD机试 - 相同数字组成图形的周长 - 矩阵(Java 2023 B卷 100分)

目录 专栏导读一、题目描述二、输入描述三、输出描述四、Java算法源码五、效果展示1、输入2、输出 华为OD机试 2023B卷题库疯狂收录中&#xff0c;刷题点这里 专栏导读 本专栏收录于《华为OD机试&#xff08;JAVA&#xff09;真题&#xff08;A卷B卷&#xff09;》。 刷的越多…

docker容器

虚拟化产品 1.奇居架构 2.原生架构 1.支持仿真虚拟化&#xff08;对系统硬件没有要求&#xff0c;性能最低&#xff09;vmware个人在windows支持 vmware workstationvmware fusion MAC2.全虚拟化产品&#xff0c;直接使用物理硬件、性能高 exic&#xff08;操作系统&#xff0…

CentOS 7 制作openssl 1.1.1w 版本rpm包 —— 筑梦之路

源码下载地址&#xff1a; https://www.openssl.org/source/openssl-1.1.1w.tar.gz 参考之前的文章&#xff1a; openssl 1.1.1L /1.1.1o/1.1.1t rpm包制作——筑梦之路_openssl的rpm包_筑梦之路的博客-CSDN博客 直接上spec文件&#xff1a; Name: openssl Version: 1.1…

【差旅游记】初见乌海湖

哈喽&#xff0c;大家好&#xff0c;我是雷工。 最近在乌海出差&#xff0c;有幸见到了传说中在沙漠中看海的“黄河明珠”——乌海湖。 前段时间一直有点忙&#xff0c;现在有点时间&#xff0c;趁还没忘光&#xff0c;简单整理记录下。 那是在上个月&#xff0c;2023年8月8号…

【大虾送书第十一期】适合新手自学的网络安全基础技能“蓝宝书”:《CTF那些事儿》

目录 &#x1f96e;写在前面 &#x1f96e;内容简介 &#x1f96e;读者对象 &#x1f96e;专家推荐 &#x1f96e;目录 &#x1f96e;文末福利 &#x1f990;博客主页&#xff1a;大虾好吃吗的博客 &#x1f990;专栏地址&#xff1a;免费送书活动专栏地址 写在前面 CTF比赛是快…

Leetcode 887. 鸡蛋掉落

文章目录 题目代码&#xff08;9.25 首刷看解析&#xff09; 题目 Leetcode 887. 鸡蛋掉落 代码&#xff08;9.25 首刷看解析&#xff09; class Solution { public:unordered_map<int, int> memo;int superEggDrop(int K, int N) {return dp(K, N);}int dp(int k, int…

【从入门到起飞】JavaSE—方法引用

&#x1f38a;专栏【JavaSE】 &#x1f354;喜欢的诗句&#xff1a;更喜岷山千里雪 三军过后尽开颜。 &#x1f386;音乐分享【The truth that you leave】 &#x1f970;欢迎并且感谢大家指出我的问题 文章目录 &#x1f354;概述&#x1f354;注意&#x1f388;如何确定是否是…

Java实现byte数组与Hex互转

十六进制字符的输出大写字符&#xff1a;0123456789ABCDEF 十六进制字符的输出小写字符&#xff1a;0123456789abcdef下面使用十六进制大写字符。 1、方式1 public class HexStringUtils {private static final char[] HEX_CHAR_TABLE {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B,…

LabVIEW在运行时调整表控件列宽

LabVIEW在运行时调整表控件列宽 如何在LabIEW中运行时调整表控件的列宽大小&#xff1f; 在VI运行时&#xff0c;有两种不同的方法可以更改表中列的宽度。首先&#xff0c;可以使用鼠标手动更改它们;其次&#xff0c;可以从框图中以编程方式更改它们。 手动更改列宽 只有在…

Feign 使用篇

Feign是一个声明式的HTTP客户端工具&#xff0c;它简化了在分布式系统中进行服务间通信的过程。开发人员可以使用Feign来定义接口&#xff0c;然后通过该接口来调用远程服务&#xff0c;就像调用本地方法一样简单。 目录 Feign的一些关键特性和概念&#xff1a;openfeign 对比 …

【高云FPGA系列教程(11):MultiButton按键驱动模块移植】

文章目录 1. MultiButton简介2. MultiButton代码获取3. MultiButton移植4. 测试与运行本文是高云FPGA系列教程的第11篇文章。 1. MultiButton简介 MultiButton, 一个小巧简单易用的事件驱动型按键驱动模块,可无限量扩展按键,按键事件的回调异步处理方式可以简化你的程序结构…

https跳过SSL认证时是不是就是不加密的,相当于http?

https跳过SSL认证时是不是就是不加密的,相当于http?&#xff0c;其实不是&#xff0c;HTTPS跳过SSL认证并不相当于HTTP&#xff0c;也不意味着没有加密。请注意以下几点&#xff1a; HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;本质上是在HTTP的基础上…

zabbix

利用一个优秀的监控软件可以: 通过一个友好的界面进行浏览整个网站所有的服务器状态 可以在 Web 前端方便的查看监控数据 可以回溯寻找事故发生时系统的问题和报警情况 zabbix 是什么&#xff1f; zabbix 是一个基于 Web 界面的提供分布式系统监视以及网络监视功能的企业级…

数字人惯性动作捕捉技术服务,激发吉祥物IP创新活力

近日&#xff0c;2023年成都市全国科普日主场活动启动仪式中&#xff0c;全球首发全国首个科普数字人形象大使“科普熊猫”&#xff0c;在大会活动现场&#xff0c;数字人“科普熊猫”结合惯性动作捕捉技术&#xff0c;与现场主持人、观众进行实时互动交流&#xff0c;以虚实结…

maven入门

作用 项目管理工具&#xff1a;依赖管理&#xff0c;项目构建 具体解决的问题 便于添加依赖自动化构建项目多模块开发 相关概念 本地仓库-》私服-》镜像/远程仓库&#xff08;中央仓库&#xff09; 依赖 依赖的范围 compiletestprovidedruntimesystem主程序是否是否否测…