1 题目描述

给定一个整数n，求以1 … n为节点所组成的二叉搜索树（BST）共有多少种情形？

例子1：

输入：3

输出：5

释义：

题目出处：

2 解决思路

先拿n=3时举个例：

a）root为1时，2、3仅可放在右子树；

b）root为2时，1放左子树，3放右子树；

c）root为3时，1、2仅可放在左子树。

总数为此三种加起来。

至于子树为两个节点的情况，再拿n=2时按上述步骤去处理。

所以可以看到规律，对于n的情形，采用如下步骤计算：

a）root为1时，2…n仅可放在右子树；

b）root为2时，1放左子树，3…n放右子树；

…

x）root为i时，1…i-1这i-1个节点放左子树，i+1…n这n-i个节点放右子树；

…

对于上述情况，递归计算即可，最后将各结果加起来，返回条件为n=0或n=1，返回为1。

改进：

上述递归计算时，对用到的子树计算结果有大量重复计算的情形，因递归较深，这样非常耗时。我们可以借助一个map来存储算过的值，这样不同的值仅计算一次。