给定一个值n,能构建出多少不同的值包含1...n的二叉搜索树(BST)?
例如
给定 n = 3, 有五种不同的二叉搜索树(BST)
这果然是一道easy的题目,因为纯靠数学推导,我们用f(n)表示对n的求解结果,在草稿上画画,你就知道
f(1) = 1;
f(2) = f(1)+f(1);
f(3) = f(2)+f(1)f(1)+f(2);
f(4) = f(3)+f(1)f(2)+f(2)f(1)+f(3)
f(5) = f(4)+f(1)f(3)+f(2)f(2)f(3)*f(1)+f(4)
因此我么就能够总结出规律了,代码如下:
public class Solution {