leetcode-不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路:

1
2
3
4
5
6
7
8
9
10
11
12
f(n)=
    1:f(0)*f(n-1)       1为根结点
    2:f(1)*f(n-2)		 2为根结点
    3:f(2)*f(n-3)		 3为根结点
    4:f(3)*f(n-4)		 4为根结点
    ...		
    n:f(n-1)*f(0)		 n为根结点

          
    f(0)=1;f(1)=1;f(2)=2;   //初始条件
               
    f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=2+1+2=5;

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numTrees(int n) {
           
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int [] arr= new int[n+1];
        arr[0]=1;
        arr[1]=1;
        arr[2]=2;
        for(int i =3;i<=n;i++){
            int temp = 0;
            while(temp <=i-1){
                arr[i]+=arr[temp]*arr[i-temp-1];
                temp++;
            }
        }    
        return arr[n];
    }
}