博客网站需求分析,西安免费做网站公司,广东网站建设需要多少钱,上海专业网站建设机构跟着carl学算法#xff0c;本系列博客仅做个人记录#xff0c;建议大家都去看carl本人的博客#xff0c;写的真的很好的#xff01; 代码随想录 LeetCode#xff1a;96.不同的二叉搜索树 给你一个整数 n #xff0c;求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉… 跟着carl学算法本系列博客仅做个人记录建议大家都去看carl本人的博客写的真的很好的 代码随想录 LeetCode96.不同的二叉搜索树 给你一个整数 n 求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种返回满足题意的二叉搜索树的种数。 示例 1 输入n 3 输出5 示例 2 输入n 1 输出1 以n 3为例dp[3] dp[2] * dp[0] dp[1] * dp[1] dp[0] * dp[2]三个结点的二叉排序树的种类 左子树为两个结点的种类 * 右子树为0个结点的种类 左子树为1个结点的种类 右子树为1个结点的种类 左子树为0个结点的种类 * 右子树为2个结点的种类递推公式dp[i] dp[j - 1] * dp[i - j]j作为头节点j - 1作为左子树的结点个数i - j作为右子树的结点个数 public int numTrees(int n) {int[] dp new int[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];}
