numTrees

Leetcode

---

题意为：输入一个正整数，输出有该数量结点的二叉搜索树的数量。
解题思路如下：从1到n，分别做root结点。对于根节点为1的情况，它只有右子树。
对于根节点为2的情况，它有1棵左子树和n-2个节点组成的右子树。。。以此类推。
得到：

$$C_n=C_{n-1}*C_0+C_{n-2}*C_1+...+C_0C_{n-1}$$
即
$$C_n=\sum_{k=0}^nC_{k}*C_{(n-1)-k}$$
那么可以发现其实计算项是对称的，可以以此稍微降低复杂度：
对于偶数：只需要计算一半的项，然后*2即可；对于奇数，除中间的数不*2之外，其余*2再相加即可。

/*
*File:numTrees.c:
*Author:0HP
*Date:20200222
*Purpose:to solve the problem in Leetcode
*https://leetcode.com/problems/unique-binary-search-trees/
*/
#include<stdio.h>
#include<stdlib.h>
int numTrees(int n){
  if(n<3){return n;}
  int *a;
  a=(int*)malloc(sizeof(int)*(n+1));
  a[0]=1;a[1]=1;a[2]=2;
  for(int i=3;i<n+1;++i)
  {
    int half=i/2;
    a[i]=0;
    if(i%2==0)
    {
      for(int j=0;j<half;++j)
      {
        a[i]=a[i]+a[i-j-1]*a[j];
      }
      a[i]=a[i]<<1;
    }
    else
    {
      for(int j=0;j<half;++j)
      {
        a[i]=a[i]+a[i-j-1]*a[j];
      }
      a[i]=a[i]*2+a[half]*a[half];
    }
  }
  return a[n];
}
int main ()
{
  printf("%d",numTrees(3));
}