96.不同的二叉搜索树

简介: 本题探讨了如何计算由 `n` 个节点组成的二叉搜索树的种类数。通过动态规划(DP)方法,定义 `dp[i]` 表示由 `i` 个节点组成的二叉搜索树的数量。递推公式为 `dp[i] += dp[j - 1] * dp[i - j]`,其中 `j` 为根节点值,`j-1` 和 `i-j` 分别表示左、右子树的节点数。初始化 `dp[0]=1`,遍历顺序为先节点总数后根节点值。最终返回 `dp[n]` 即为结果。代码实现简洁高效,时间复杂度为 O(n²)。

题目: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];
    }
};
相关文章
|
JSON 搜索推荐 网络协议
玩转curl指令—测试简单的HTTP接口
玩转curl指令—测试简单的HTTP接口
3070 0
|
算法 安全 数据安全/隐私保护
DSA与RSA的区别、ECC(椭圆曲线数字签名算法(ECDSA))
DSA与RSA的区别、ECC(椭圆曲线数字签名算法(ECDSA))
2117 0
|
数据采集 机器学习/深度学习 存储
一文讲清数据清洗的十大常用方法
本文详解数据清洗十大常用方法与实战技巧,涵盖缺失值填补、重复值处理、异常值检测、数据标准化、文本清洗、数据脱敏等关键操作,助你高效提升数据质量,解决“脏乱差”问题。
2314 10
一文讲清数据清洗的十大常用方法
|
Web App开发 Rust 前端开发
WebAssembly 与 Java 结合实操指南 基于最新工具链的跨语言开发实践教程
WebAssembly与Java集成实操指南 本文基于2024年最新工具链(GraalVM、TeaVM、Wasmtime),提供两种Java与Wasm结合的实践方案: Java调用Wasm模块:通过Rust编写高性能加密算法并编译为Wasm,在Java中利用Wasmtime运行时进行调用,实现6.7倍的性能提升。重点演示了Wasm内存模型操作和指针传递机制。 Java编译为Wasm:使用TeaVM将Java科学计算代码编译为Wasm模块,供浏览器前端直接调用。包含完整的Maven配置和前端调用示例,特别适合
1082 5
|
网络协议 开发工具 git
解决 git 报错 “fatal: unable to access ‘https://github.com/.../.git‘: Recv failure Connection was rese
在使用 Git/Git小乌龟 进行代码管理的过程中,经常会遇到各种各样的问题,其中之一就是在执行 git clone 或 git pull 等操作时出现 “fatal: unable to access ‘https://github.com/…/.git’: Recv failure Connection was reset” 的报错。这个问题通常是由网络连接问题或代理设置不正确导致的。在我的个人使用经验中,我亲自尝试了四种方法,它们都能够有效地解决这个报错。个人比较推荐方法二。
10999 1
|
SQL 关系型数据库 MySQL
MySQL操作利器大公开!这几款客户端让你事半功倍
本文介绍了多种MySQL数据库管理工具,包括命令行工具、图形化用户界面(GUI)工具和Web界面工具。主要工具有: 1. **Navicat for MySQL**:功能强大,支持多种数据库管理任务,但需付费。 2. **DBeaver**:开源免费,支持多种数据库,安装包较大。 3. **MySQL Workbench**:官方提供的图形化工具,适合MySQL全家桶用户。 4. **HeidiSQL**:轻量级Windows客户端,简单易用。 5. **phpMyAdmin**:基于Web的管理工具,易于部署和使用。 6. **SQLyog**:适用于Windows,功能丰富,有免费
3241 3
|
网络协议 Linux 网络安全
Tun/Tap接口指导
Tun/Tap接口指导
1405 1