leetcode96. 不同的二叉搜索树

leetcode96. 不同的二叉搜索树

四月 11, 2020

leetcode96. 不同的二叉搜索树

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

示例:

输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

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

思路

开始我都没有想到用动态规划,因为之前也不熟,所以想用递归解,但是最后就演变成了动态规划。
比如n=4,我需要知道他的左右子树可以怎么构成(0,3)(1,2)(2,1)(3,0),因为去掉根节点左右子树一共三个节点。我只需要知道3个节点和2个节点的情况，于是就递归求解。求出n=3时候的状态。最后自底向上解决。

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
27
28
29
30
31
32
33
class Solution {
    public int numTrees(int n) {
        if(n==0)return 1;
        int[]map=new int[n+2];
        map[1]=1;
        map[2]=2;
        int mid=n/2;
        for(int i=3;i<=n;i++){
            solve(map,i);
        }
        return map[n];
    }
    public void solve(int[]map,int cur){
        //一个建立map的方法
        int mid=cur/2;
        int mid2=-1;
        int sum=0;
        for(int i=1;i<=mid;i++){
                int left=i-1;
                int right=cur-i;
                if(left==0)left=1;
                if(right==0)right=1;
                sum+=(map[left]*map[right]);
        }
        sum*=2;
        if((cur&1)==1){
            //奇数
            int i=(cur+1)>>1;
            sum+=(map[i-1]*map[cur-i]);
        }
        map[cur]=sum;
    }
}

第一次做出来动态规划，很激动啊。
leetcode 64/100