Unique Binary Search Trees

用户1624346

发布于 2018-04-17 16:58:20

5070

发布于 2018-04-17 16:58:20

文章被收录于专栏：calmound

问题：n个结点总共有多少个二叉搜索树分析：n=1,sum1=1 n=2,sum2=2; n=3,sum3=2(头结点为1)+1(头结点为2)+2(头结点为3) n=4,sum4=5(头结点为1,sum3)+2(头结点为2,sum1*sum2)+2(头结点为3,sum2*sum1)+5(头结点为4,sum3) n=5,sum5=14(sum4)+5(sum1*sum3)+4(sum2*sum2)+5(sum1*sum3)+14(sum4) .....以此类推

class Solution {
public:
    int numTrees(int n) {
        int a[100]={0},i,j;
        a[0]=1;
        a[1]=1;
        for(i=2;i<=n;i++)
        {
            for(j=0;j<i;j++)
            {
                a[i]+=a[j]*a[i-1-j];
            }
        }
         return a[n];
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2014-08-04 ，如有侵权请联系 cloudcommunity@tencent.com 删除

编程算法