96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/

题目大意：给出一个正整数n，求出共有多少棵存储从1到n的二叉搜索树，例如：假设n等于3，则结果为5棵。

解题思路：手动画出n等于1，2，3，4时共有多少颗二叉搜索树，找出规律：相当于每次先找出从1到n中任意一个数作为根节点，那么左子树和右子数的数字个数就确定了。

具体做法：我们申请一个数组result[n+1]，result[i]表示有i个节点时二叉搜索树有result[i]棵，最后result[n]就是我们想要的结果。我们从i=0开始迭代，由于选1和选i作为根节点是具有对称性的，选2和选i-1是具有对称性的，所以只需要迭代前半部分再乘以2。但是这里要注意i为奇数和偶数的时候是不同的，奇数时我们不能再乘以2，而是单独处理。

代码如下：

class Solution {
public:
    int numTrees(int n) {
        if(n <= 0) return 0;
        int result[n+1];
        for(int i = 0; i <= n; i++)
            result[i] = 0;

        result[1] = 1;
        for(int i = 2; i <= n; i++)
        {
            for(int j = 1; j <= i/2; j++)
            {
                if(j == 1)
                    result[i] += result[i-j];
                else
                {
                    int tmp = result[j-1] * result[i-j];
                    result[i] += tmp;
                }
            }
            result[i] *= 2;
            if(i%2)
            {
                int tmp = result[i/2] * result[i/2];
                result[i] += tmp;
            }
        }
        return result[n];
    }
};

96. Unique Binary Search Trees

推荐阅读