- Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
- For example,
- Given n = 3, there are a total of 5 unique BST's.
- 1 3 3 2 1
- \ // / \ 3 2 1 1 3 2
- // \ 2 1 2 3
给定一个数字 n, 返回 n 个节点一共有多少种二叉搜索树.
思路: 一开始我的思路是使用排列组合得出每个二叉搜索树, 后来看到题目是可以使用 DP. 然后查了下, 发现应该使用一种卡特兰数的东西.
关于卡特兰数可以看这篇博文: https://www.cnblogs.com/code-painter/p/4417354.html
对于给定的 n, 我们可以分别求当 1,2,3....n 为根的时候的搜索二叉树的数目再求和.
当第 k 个数作为根的时候, 左子树有 k-1 个节点, 右子树有 n-k 个节点.
所以此时的搜索二叉树的数目为 dp[k-1]*dp[n-k](dp[i] 为当 n=i 的时候拥有的二叉搜索树的数目)
当 n=0 的时候 dp[0] = 1, 因为空树也算是一种二叉树, 当只有一个节点的时候 dp[1]=1.
当有两个节点的时候分两种情况, 以 1 为根的时候, 和以 2 为根的时候.
- dp[2] = dp[0]*dp[1] // 当根为 1 的时候
- + dp[1]*dp[0] // 当根为 2 的时候
当有三个节点的时候分三种情况:
- dp[3] = dp[0]*dp[2] //1 为根节点
- +dp[1]*dp[1] //2 为根节点
- +dp[2]*dp[0] //3 为根节点
实现代码如下:
- public class Unique_Binary_Search_Trees {
- public static int numTrees(int n) {
- if(n==0) return 0;
- if(n==1) return 1;
- int[] result = new int[n+1];
- result[0] = 1;
- result[1] = 1;
- result[2] = 2;
- if(n<3){
- return result[n];
- }
- for(int i=3;i<=n;i++){
- for(int k=1;k<=i;k++){
- result[i] += result[k-1]*result[i-k];
- }
- }
- return result[n];
- }
- public static void main(String[] args) {
- System.out.println(numTrees(3));
- }
- }
来源: http://www.bubuko.com/infodetail-2948068.html