汉中做网站的公司电话,wordpress主题安装全解析,王占山人物简介,网站开发需要多少人给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种#xff1f;返回满足题意的二叉搜索树的种数。 示例 1#xff1a; 输入#xff1a;n 3
输出#xff1a;5示例 2#xff1a;
输入#xff1a;n 1
输出#xff1a;1提…给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 示例 1 输入n 3
输出5示例 2
输入n 1
输出1提示
1 n 19 思路
本题可采用动态规划解决。dp[ i ] 表示从 节点 1 到节点 i 分别作为根节点 所形成的二叉搜索树的种数之和。
确定递推公式dp[ i ] dp [ j -1 ] * dp[ i - j ]其中 j 是当前作为根节点的节点取值范围是 [ 1 i ]当 节点 j 作为根节点时其 左子树的节点个数为 j -1所以左子树形成的二叉搜索树的种数为 dp[ j - 1 ]其右子树的节点个数为 i - j所以右子树形成的二叉搜索树的种数为 dp [ i - j ]故节点 j 作为根节点时形成的二叉搜索树的种数为 dp[ j - 1] * dp[ i - j ]。
初始化时 0 个节点 时令 dp[ 0 ] 为 1表示一棵空树。 遍历顺序由于 dp[ i ] 依赖 dp[ j-1 ] 和 dp [ i - j ]所以要计算 dp[ n ]则需要先计算 dp [ 1 ] ~ dp[ n- 1 ]因此要从前往后依次遍历计算出每一个 dp [ i ]1 i n。
代码
class Solution {public int numTrees(int n) {//初始化 dp,dp[i]表示从节点1到节点i分别作为根节点组成的二叉搜索树的种数之和int[] dp new int[n1];//初始化dp[0]dp[0] 1;for(int i1;in;i){for(int j1;ji;j){//以 j 为根节点的二叉搜索树的左子树有 j-1 个节点右子树有 i-j 个节点dp[i] dp[j-1]*dp[i-j];}}return dp[n];}
}
参考代码随想录
