leetcode：Unique Binary Search Trees

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

注意：二分查找树的定义是，左子树节点均小于root，右子树节点均大于root！不要想当然地将某个点作为root时，认为其他所有节点都能全部放在left/right中，除非这个点是 min 或者 max 的。

分析：本题其实关键是递推过程的分析，n个点中每个点都可以作为root，当 i 作为root时，小于 i 的点都只能放在其左子树中，大于 i 的点只能放在右子树中，此时只需求出左、右子树各有多少种，二者相乘即为以 i 作为root时BST的总数。

开始时，我尝试用递归实现，但是超时了，可见系统对运行时间有要求。因为递归过程中存在大量的重复计算，从n一层层往下递归，故考虑类似于动态规划的思想，让底层的计算结果能够被重复利用，故用一个数组存储中间计算结果（即 1~n-1 对应的BST数目），这样只需双层循环即可，代码如下：

class Solution {

public:

    int numTrees(int n) {

        vector<int> num;

        num.push_back(1);  //在容器尾端插入一项数据，设置num[0]=1

        for(int i=1; i<=n; i++){

            num.push_back(0);  //每次先将num[i]设置为0

            if(i<3)

                num[i]=i;  //易知num[1]=1,num[2]=2

            else{

                for(int j=1; j<=i; j++)

                    num[i]+=num[j-1]*num[i-j];  //j为root节点，其左子树种数为j-1，右子树种数为i-j

            }

        }

        return num[n];

    }

};

　其他解法：

1、1ms in C++ By Using Theorem From Graph Theory

This is my code. I use the property that the number of unique binary trees or n vertex is

{(2n)(2n-1)(2n-2)....(n+2)}/{(n)(n-1)....(2)(1)}

class Solution {

public:

    int numTrees(int n) {

        long long result = 1;

        long long temp = 1;

        for(int i = 2*n; i > n; i--){

            result *= i;

            temp *= (i-n);

            if (result % temp == 0){

                result /= temp;

                temp = 1;

            }

        }

        return result/(n+1);

    }

};

2、2ms c++ using dp（动态规划）

class Solution {

public:

  int numTrees(int n){

int arr[n+1][n+1];

memset(arr,0,sizeof(arr));

for(int len=1; len<=n; len++){

    for(int j=1; j<=n-len+1; j++){

        if(len == 1) arr[len][j] = 1;

        else{

            arr[len][j] += arr[len-1][j+1];

            arr[len][j] += arr[len-1][j];

            for(int k=1;k<len;k++) arr[len][j] += (arr[k][j]*arr[len-k-1][j+k+1]);

        }

    }

}

return arr[n][1];

}

};

3、

class Solution {

public:

  int numTrees(int n) {

     if(n==0) return 0;

        int s[n+1];

        int r;

        s[0] = 1;

        for(int i=1; i<n+1; i++)

        {

            s[i] = 0;

            for(int l=0; l<i; l++)

            {

                r = i-1-l;

                s[i] = s[i]+s[l]*s[r];

            }

        }

        return s[n];

    }

};

巴特西

leetcode：Unique Binary Search Trees

最新文章

热门文章