算法力扣刷题记录 八十三【96.不同的二叉搜索树】
前言
动态规划第9篇。记录 八十三【96.不同的二叉搜索树】。
一、题目阅读
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例 2：
输入：n = 1
输出：1
提示：
1 <= n <= 19
二、尝试实现
2.1分析题目，确定方法
- 拿到题目之后，要看用什么方法，而不是根据章节分类直接有个思路去想。
- 题目问有多少种二叉搜索树，按照示例想：这是从一个集合中选择元素，那么回溯能不能搜索出来呢？回溯题目都能构造一个树形结构。但是在构造树形结构时，发现没有办法筛掉元素，如下：
- 所以回溯不可能实现。但是画树形结构中想到：
-
如果选择1作为根节点，那么剩下的[2,3]肯定在右子树中，那么元素个数是2能构成2种右子树。所以1为根节点的二叉搜索树有2种。
-
如果选择2作为根节点，那么剩下的[1]肯定在左子树中，那么元素个数是1能构成1种左子树；剩下的[3]肯定在右子树中，那么元素个数是1能构成1种右子树。所以2为根节点的二叉搜索树有1种。
-
如果选择3作为根节点，那么剩下的[1,2]肯定在左子树中，那么元素个数是2能构成2种左子树。所以3为根节点的二叉搜索树有2种。
-
最后：求和得出n=3时，有5种二叉搜索树。
-
这个过程是状态的转移。有递推公式，所以是动态规划题目。
2.2动态规划思路
- 定义dp数组，确定含义。dp[i]代表当组成一个树（可以是子树）的元素个数是i时，可以有dp[i]种二叉搜索树。
- 确定递推公式：根据2.1中的图和过程——需要一个变量j，从1开始遍历到 i，有个求和的过程。对于每个j来说：
- leftnum代表以 j 为根节点，左子树中的元素个数；dp[leftnum]就是左子树的种类。
- rightnum代表以 j 为根节点，右子树中的元素个数；dp[rightnum]就是右子树的种类。
- 以 j 为根节点的二叉搜索树：dp[leftnum] * dp[rightnum] 种。
- 初始化：dp[0] =1；代表当左/右子树没有元素时，只有1种表示。dp[1] = 1；
- 遍历顺序：
- 第一层遍历：i 从2开始，直到n。代表总的节点数；
- 第二层遍历：j 从1开始，直到 i。注意：是i，不是n。代表以j为根节点的二叉搜索树，求其左右子树有多少种；
2.3 代码实现【动态规划】
class Solution {
public:int numTrees(int n) {//定义dp数组。含义：当组成一个树节点个数是i，构成的二叉搜索树有dp[i]种vector<int> dp(n+1,0);//初始化：dp[0] = 1;//当左/右子树没有元素时，只有1种表示。dp[1] = 1;//当元素个数是1，组成的二叉搜索树有1种//遍历顺序for(int i = 2;i < dp.size();i++){for(int j = 1;j <= i;j++){//以j作为根节点的数值，那么左子树的元素个数是int leftnum = j-1;//以j作为根节点的数值，那么右子树的元素个数是int rightnum = i-j;dp[i] += dp[leftnum]*dp[rightnum];}}return dp[n];}
};
三、参考学习
96.不同的二叉搜索树 参考学习链接
- 参考给的思路和实现与二、尝试实现一样。关键就是：2.1中由一个不正确的方法，模糊的感觉到有状态转移，所以尝试动态规划。
- 分析一下时间复杂度：两层for循环：O(N2)；
- 空间复杂度：需要创建n+1大小的dp数组，所以O(N);
四、总结
96.不同的二叉搜索树 的重点是2.1分析题目，确定方法。注意 j 的遍历到 i 为止。
（欢迎指正，转载标明出处）