LeetCode [96] 不同的二叉搜索树

我是先刷了【95】不同的二叉搜索树(4个小时+才ac,我是不是废了)，然而96题更简单，只需要不同二叉树的总个数就行，95需要把所有的二叉树都列出来。所以第一种做法就是把95的思路拿过来了。

第一种方法

采用了递归的方法，题解如下:
首先枚举n为0,1的情况，大致思路如下，输入为n时，CreateTree(n)表示从1…n每一个分别做一次root结点，当i(0<=i<=n)为根节点时，它的左子树为(0…i)，有l种case；右子树为(i+1, n)，有r种case；所以当i为root结点时，有l*r中搜索二叉树case，对应左右子树为0的情形，需要特殊处理。从i=0开始遍历，到n-1，每次都把case累加到num中即可。

	int res;
    int numTrees(int n) {
        if(n <= 1) return n;
        return createTree(n);
    }
    int createTree(int n)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        int num = 0;
        for(int i = 0; i <=  n - 1; i++)    
        {
            int l = createTree(i, v);
            int r = createTree(n - i - 1, v);
            if(l != 0 && r != 0)
                num += l * r;
            else if(l == 0 && r != 0)
                num += r;
            else if(l != 0 && r == 0)
                num += l;
        }
        return num;
    }
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

高高兴兴一提交，大于14直接超时。。。。那只能改了。

int res;
    int numTrees(int n) {
        if(n <= 1) return n;
        return createTree(n);
    }
    int createTree(int n)
    {
        if(n == 0) return 0;
        if(n == 1) return 1;
        if(n == 2) return 2;
        int num = 0;
        for(int i = 0; i <=  n - 1; i++)    
        {
            int l = createTree(i, v);
            int r = createTree(n - i - 1, v);
            if(l != 0 && r != 0)
                num += l * r;
            else if(l == 0 && r != 0)
                num += r;
            else if(l != 0 && r == 0)
                num += l;
        }
        return num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

偷懒的办法，加了n=2的情形，勉强可以通过，但是觉得不是这回事儿，这有点像是加表了，没有改变实质性问题。
既然每次都会用到上次的计算结果，自然会想到找个vector把历史记录存下来。

改进版本

int res;
    int numTrees(int n) {
        if(n <= 1) return n;
        vector<int> v{0, 1, 2};
        return createTree(n, v);
    }
    int createTree(int n, vector<int> &v)
    {
        if(n == 0)
            return 0;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        // v.size() > n + 1说明此时是回溯进来的，此时v中已经存下n,可以直接返回
        if(v.size() > n + 1)
            return v[n];
        int num = 0;
        for(int i = 0; i <=  n - 1; i++)    
        {
            int l = createTree(i, v);
            int r = createTree(n - i - 1, v);
            if(l != 0 && r != 0)
                num += l * r;
            else if(l == 0 && r != 0)
                num += r;
            else if(l != 0 && r == 0)
                num += l;
        }
        if(v.size() <= n)//v.size()<=n说明，此次计算为n的情形，需要记录在v中
            v.push_back(num);
        return num;
    }
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

速度明显会快许多，直接ac.
但是代码依然不够简练，需要重构，此时要尽量追求代码尽可能简单易懂。
首先v的保存记录可以直接保存，不用每次判断是否为size<=n的情形。
另外num计算这个地方，感觉也有点别扭，num = lr + r(l=0) + l(r=0), 其实可以把l或者r等于0的地方合并到lr中，把返回0的地方改为返回1.这样就不用额外考虑了。
代码修改之后，清爽了许多。

自己的答案最终版

int numTrees(int n) {
        if(n <= 1) return n;
        vector<int> v(n+1, 0);
        v[0] = 1;
        v[1] = 1;
        return createTree(n, v);
    }
    int createTree(int n, vector<int> &v)
    {
        if(v[n])
            return v[n];
        int num = 0;
        for(int i = 0; i <=  n - 1; i++)    
        {
            int l = createTree(i, v);
            int r = createTree(n - i - 1, v);
                num += l * r;
        }
        v[n] = num;
        return num;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

官方解答更为精炼，但是需要推理