算法练习：不同的二叉搜索树（动态规划）
2022-06-01 本文已影响0人
cofbro
一.前言
LeetCode题目：96. 不同的二叉搜索树
给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。
示例 1：
输入：n = 3
输出：5
示例2：
输入：n = 1
输出：1
题目很简洁，但是分析起来却有点复杂，首先搞清楚什么是二叉搜索树。二叉搜索树分为左子树和右子树，左子树还能再分为左子树和右子树，就像这样：
二叉搜索树有三个条件：
- 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值
- 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值
- 它的左、右子树也分别为二叉搜索树
二.分析思考
我们将dp数组定义为1 到 n 互不相同的二叉搜索树的个数，先来尝试写写 n = 1 和 n = 2的情况
这两个其实还挺简单的，再来看看 n = 3 的时候
这个时候不同的二叉搜索树就有5个了，我们来看看这五个是怎么根据前面的结果推导出来的。此图片中前两棵树是根据dp[2]中的第一个二叉搜索树得出来的，他们结构都是一样的，都是没有左子树，右子树有两个结点。而dp[3]中的第三和第四棵树同理和dp[2]中的第二棵树结构相同。
那么dp[3]中最后一棵树是怎么来的呢，我们将眼光放宽一点，这时候会发现它和dp[1]中那棵树结构很相似！
继续探索一下这个规律：
- 二叉搜索树当以
1为起点时，它的个数为右子树的个数dp[2]； - 二叉搜索树当以
2为起点时，它的个数为右子树的个数dp[1] * 左子树的个数dp[1]； - 二叉搜索树当以
3为起点时，它的个数为左子树的个数dp[2]；
则总共的二叉搜索树为：dp[2] + dp[1] * dp[1] + dp[2]
注：定义dp[0] = 1，使之符合下面通式的规律
我们将这个规律扩展到 n，我们需要计算出从 1 到 n 为起点的每一个二叉搜索树的个数，因此需要循环来遍历，则总共的二叉搜索树为：dp[i] += dp[i - j] * dp[j -1]，其中i 为外层循环且i <= n，j 为内层循环且 j <= i。
为了验证一下这个规律，我们继续往下写一组二叉搜索树，当n = 4时
其中二叉搜索树为个数为：dp[0] * dp[3] + dp[1] * dp[2] + dp[2] * dp[1] + dp[3] * dp[0] = 14，确实符合上述规律...
三.代码
分析完了，现在就来看看代码，如果还有点疑惑说不定看了代码就豁然开朗了。
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= n; i++){
for(int j = 1; j <= i; j++){
dp[i] += dp[i - j] * dp[j -1];
}
}
return dp[n];
}
}
ps.虽然代码只有这么点，但是分析和思考过程却远远不止这点，要想掌握动态规划还得多加练习和总结啊。
