鹿泉外贸网站建设,湖南做网站问磐石网络专业,嘉兴app开发公司,成都网站建设 平易云给定一个整数 n#xff0c;求以 1 ... n 为节点组成的二叉搜索树有多少种#xff1f;
示例:
输入: 3 输出: 5 解释: 给定 n 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 …给定一个整数 n求以 1 ... n 为节点组成的二叉搜索树有多少种
示例:
输入: 3 输出: 5 解释: 给定 n 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3
思路dp[n]代表答案则dp[n]
左子树1节点右子树n-1节点
左子树2节点右子树n-2节点
................................
左子树n-1节点右子树1节点
所有情况加起来。
public 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[j - 1] * dp[i - j];}}return dp[n];}
}
官方有一个数学太强了。
